title: finding the number of integer points under a triangle, square and circle
body: <p>for circle i have tried to check for all points within radius distance from center.For  square, i test for all points from bottom-left-corner to upper-right-corner and for triangle i  test the signs of determinants as suggested <a href="http://in.answers.yahoo.com/question/index?qid=20110614030208AATF7aU" rel="nofollow">here</a>. I get correct answer while i enter individual values i.e either 1 cirlce or 1 square or 1 triangle , but not when there are >1 of them. E.g for the case: </p>
  
  <pre><code>C 10 10 3
  S 9 8 4
  T 7 9 10 8 8 10
  </code></pre>
  
  <p>where C is circle, S is square and T is triangle,and (10,10) is center of circle with radius 3. (9,8) is the left-most corner of square of side 4 and (7,9),(10,8) and (8,10) are the three vertices of the triangle , the total distinct points covered by them is 34 but i am getting 37. </p>
  
  <p>Here's what i've tried:</p>
  
  <pre><code>typedef pair&lt;int,int&gt; point;
  set&lt;point&gt;myset;
  set&lt;point&gt;::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 &gt;= 0) ^ (y &lt; 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",&amp;t);
  while(t--)
  {
      myset.clear();
      scanf("%d",&amp;n);
      for(i=0;i&lt;n;i++)
      {
          scanf("%c",&amp;dump);
          scanf("%c",&amp;shape);
          if(shape=='C')
          {
              scanf("%d %d %d",&amp;x,&amp;y,&amp;r);
              for(j=x;j&lt;=x+r;j++)
              {
                  for(k=y;k&lt;=y+r;k++)
                  {
                      point p(j,k);
                      myset.insert(p);
                  }
              }
              for(j=x-r;j&lt;x;j++)
              {
                  for(k=y-r;k&lt;y;k++)
                  {
                      point p(j,k);
                      myset.insert(p);
                  }
              }   
  
          }
          else if(shape=='S')
          {
              scanf("%d %d %d",&amp;x1,&amp;y1,&amp;len);
              for(j=x1;j&lt;=x1+len;j++)
              {
                  for(k=y1;k&lt;=y1+len;k++)
                  {
                      point p(j,k);
                      myset.insert(p);
                  }
              }
  
          }
          else
          {
              //printf("here\n");
              scanf("%d %d %d %d %d %d",&amp;ax,&amp;ay,&amp;bx,&amp;by,&amp;cx,&amp;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&lt;=xmax;j++)
              {
                  for(k=ymin;k&lt;=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)&amp;&amp;sameSign(D2,D3)&amp;&amp;sameSign(D1,D3))
                      {
                          //printf("here\n");
                          point p(j,k);
                          myset.insert(p);
                      }
                  }
              }
          }
  
      }
      printf("%d\n",myset.size());
  }
  return 0;
  }
  </code></pre>