삼각형, 사각형 및 원 아래의 정수 점 수를 확인하려면

Question

원에 대해 반경 내에서 모든 점을 확인하려고 시도했습니다. 사각형의 경우 왼쪽 하단에서 오른쪽 상단까지 모든 점을 테스트합니다. -corner와 triangle에 대해서는 determinant의 부호를 테스트하기 위해 here을 테스트합니다. 개별 값을 입력하는 동안 올바른 답을 얻습니다. 즉, 1 개 또는 1 개의 정사각형 또는 1 개의 삼각형을 입력 할 수 있지만 그 중 1 개 이상은 입력 할 수 없습니다. 경우의 예 : C는 원형 인

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

는, 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

는 무슨 일이 일어나고 있는지 나에게 명확이되도록 크게 코드를 리팩토링 후 - 나는 오류가 원 코드에 말하고 싶지만. 나는 전체 리팩토링 코드 아래에 포함했지만이에 귀찮은 부분 금액들 :

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)); 
      } 
     } 
     } 
    } 

을 Heres는

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 우리는 원에 대한 해결책을 볼 수 있습니다.