找到一個三角形，正方形和圓形下的整數點數

Question

對於圓形，我試圖檢查圓心距半徑距離內的所有點。對於正方形，我測試了從左下角到右上角的所有點-corner和三角形我測試行跡跡象建議here。當我輸入單個值即1或1平方或1個三角形時，我會得到正確的答案，但當其中有1個以上時，則不會。例如，對於情況：

C 10 10 3 
S 9 8 4 
T 7 9 10 8 8 10 

其中C是圓形，S爲正方形，T是三角形，以及（10,10）是具有半徑3（9,8）圓的中心是最左邊的角（7,9），（10,8）和（8,10）是三角形的三個頂點，它們覆蓋的總體不同點是34，但是我得到了37.

以下是我已經試過：

typedef pair<int,int> point; 
set<point>myset; 
set<point>::iterator it; 

int findDeter(int x1,int y1,int x2,int y2,int x0,int y0) 
{ 
int ret = x1*(y2-y0)-y1*(x2-x0)+(x2*y0-x0*y2) 
     -x2*(y1-y0)+y2*(x1-x0)-(x1*y0-x0*y1) 
     +x0*(y1-y2)-y0*(x1-x2)+(x1*y2-x2*y1); 
return ret; 
} 
bool sameSign(int x, int y) 
{ 
if(x==0||y==0) 
return true; 
    return (x >= 0)^(y < 0); 
} 
int main() 
{ 
int t,i,j,k,n; 
int x,y,r,x1,y1,len; 
int xmax,ymax,xmin,ymin; 
int D1,D2,D3; 
int ax,ay,bx,by,cx,cy; 
char shape,dump; 
scanf("%d",&t); 
while(t--) 
{ 
    myset.clear(); 
    scanf("%d",&n); 
    for(i=0;i<n;i++) 
    { 
     scanf("%c",&dump); 
     scanf("%c",&shape); 
     if(shape=='C') 
     { 
      scanf("%d %d %d",&x,&y,&r); 
      for(j=x;j<=x+r;j++) 
      { 
       for(k=y;k<=y+r;k++) 
       { 
        point p(j,k); 
        myset.insert(p); 
       } 
      } 
      for(j=x-r;j<x;j++) 
      { 
       for(k=y-r;k<y;k++) 
       { 
        point p(j,k); 
        myset.insert(p); 
       } 
      } 

     } 
     else if(shape=='S') 
     { 
      scanf("%d %d %d",&x1,&y1,&len); 
      for(j=x1;j<=x1+len;j++) 
      { 
       for(k=y1;k<=y1+len;k++) 
       { 
        point p(j,k); 
        myset.insert(p); 
       } 
      } 

     } 
     else 
     { 
      //printf("here\n"); 
      scanf("%d %d %d %d %d %d",&ax,&ay,&bx,&by,&cx,&cy); 
      /*a1=ax;a2=ay; 
      b1=bx;b2=by; 
      c1=cx;c2=cy;*/ 
      xmax = max(ax,max(bx,cx)); 
      ymax = max(ay,max(by,cy)); 
      xmin = min(ax,min(bx,cx)); 
      ymin = min(ay,min(by,cy)); 
      /*for each point P check if sum(the determinants PAB,PAC and PBC have the same signs)*/ 
      for(j=xmin;j<=xmax;j++) 
      { 
       for(k=ymin;k<=ymax;k++) 
       { 
        D1 = findDeter(ax,ay,bx,by,j,k); 
        //printf("D1 : %d\n",D1); 
        D2 = findDeter(bx,by,cx,cy,j,k); 
        //printf("D2 : %d\n",D2); 
        D3 = findDeter(cx,cy,ax,ay,j,k); 
        //printf("D3 : %d\n",D3); 
        if(sameSign(D1,D2)&&sameSign(D2,D3)&&sameSign(D1,D3)) 
        { 
         //printf("here\n"); 
         point p(j,k); 
         myset.insert(p); 
        } 
       } 
      } 
     } 

    } 
    printf("%d\n",myset.size()); 
} 
return 0; 
} 

Answer 1

很大程度上重構你的代碼，以便它更清楚我是怎麼回事之後 - 我想說的錯誤是在圈內代碼。我已經包括下面的完整重構代碼，但麻煩的部分金額s到這一點：

struct Circle 
{ 
    int x; 
    int y; 
    int r; 

    void add_covered_points(set<points> & pts) const 
    { 
     for(int j=x;j<=x+r;j++) 
     { 
     for(int k=y;k<=y+r;k++) 
     { 
      pts.insert(point(j,k)); 
     } 
     } 
     for(int j=x-r;j<x;j++) 
     { 
     for(int k=y-r;k<y;k++) 
     { 
      pts.insert(point(j,k)); 
     } 
     } 
    } 
}; 

這似乎從兩個矩形截面，一個以上和其他低於圓心加分。我期望的代碼看起來更象這樣：

void add_covered_points(set<points> & pts) const 
    { 
     for(int j=-r;j<=+r;j++) 
     { 
     for(int k=-r;k<=+r;k++) 
     { 
      if (j*j + k*k < r*r) 
      { 
       pts.insert(point(x+j,x+k)); 
      } 
     } 
     } 
    } 

繼承人的完整重構的情況下，供您參考

typedef pair<int,int> point; 


int findDeter(int x1,int y1,int x2,int y2,int x0,int y0) 
{ 
int ret = x1*(y2-y0)-y1*(x2-x0)+(x2*y0-x0*y2) 
     -x2*(y1-y0)+y2*(x1-x0)-(x1*y0-x0*y1) 
     +x0*(y1-y2)-y0*(x1-x2)+(x1*y2-x2*y1); 
return ret; 
} 
bool sameSign(int x, int y) 
{ 
if(x==0||y==0) 
return true; 
    return (x >= 0)^(y < 0); 
} 

struct Circle 
{ 
    int x; 
    int y; 
    int r; 

    void add_covered_points(set<points> & pts) const 
    { 
     for(int j=x;j<=x+r;j++) 
     { 
     for(int k=y;k<=y+r;k++) 
     { 
      pts.insert(point(j,k)); 
     } 
     } 
     for(int j=x-r;j<x;j++) 
     { 
     for(int k=y-r;k<y;k++) 
     { 
      pts.insert(point(j,k)); 
     } 
     } 
    } 
}; 

struct Square 
{ 
    int x1,y1,len; 
    void add_covered_points(set<points> & pts) const 
    { 
    for(int j=x1;j<=x1+len;j++) 
    { 
     for(int k=y1;k<=y1+len;k++) 
     { 
      myset.insert(point(j,k)); 
     } 
    } 
    } 
}; 

struct Triangle 
{ 
    int ax,ay,bx,by,cx,cy; 
    void add_covered_points(set<points> & pts) const 
    { 
    int xmax = max(ax,max(bx,cx)); 
    int ymax = max(ay,max(by,cy)); 
    int xmin = min(ax,min(bx,cx)); 
    int ymin = min(ay,min(by,cy)); 

    /*for each point P check if sum(the determinants PAB,PAC and PBC have the same signs)*/ 
    for(int j=xmin;j<=xmax;j++) 
    { 
     for(int k=ymin;k<=ymax;k++) 
     { 
      int D1 = findDeter(ax,ay,bx,by,j,k); 
      int D2 = findDeter(bx,by,cx,cy,j,k); 
      int D3 = findDeter(cx,cy,ax,ay,j,k); 

      if(sameSign(D1,D2)&&sameSign(D2,D3)&&sameSign(D1,D3)) 
      { 
      pts.insert(point(j,k)); 
      } 
     } 
    } 
    } 
}; 


int main() 
{ 
set<point>myset; 
int t; 
scanf("%d",&t); 
while(t--) 
{ 
    myset.clear(); 
    int n; 
    scanf("%d",&n); 
    for(int i=0;i<n;i++) 
    { 
     char dump; 
     char shape; 
     scanf("%c",&dump); 
     scanf("%c",&shape); 
     if(shape=='C') 
     { 
      Circle c; 
      scanf("%d %d %d",&c.x,&c.y,&c.r); 
      c.add_covered_points(myset); 
     } 
     else if(shape=='S') 
     { 
      Square s; 
      scanf("%d %d %d",&s.x1,&s.y1,&s.len); 
      s.add_covered_points(myset); 
     } 
     else 
     { 
      Triangle t; 
      int ax,ay,bx,by,cx,cy; 
      scanf("%d %d %d %d %d %d",&t.ax,&t.ay,&t.bx,&t.by,&t.cx,&t.cy); 
      t.add_covered_points(myset); 
     } 
    } 
} 
return 0; 
} 

Answer 2

Pick's theorem適用於室內與整數頂點計算簡單多邊形的整數關口。

Here我們可以看到解決方案的圈子。