SPOJ

题目链接:https://www.spoj.com/problems/AMR11B/en/
题目大意就是要你求图形覆盖的格点数，标记每个图形里的未标记格点（包括边界），总标记数就是覆盖的总格点数。
 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 struct node{
 5     int x;
 6     int y;
 7 };
 8 int t,n,visit[250][250];
 9 void ri(node &a)//将每个点的横纵坐标加100 
10 {
11     a.x+=100;
12     a.y+=100;
13 }
14 int po(node a,node b)//计算向量的点乘 
15 {
16     return a.x*b.x+a.y*b.y;
17 }
18 int main()
19 {
20     cin>>t;
21     while(t--)
22     {
23         cin>>n;
24         getchar();
25         for(int i=0;i<250;i++)
26         for(int j=0;j<250;j++)
27         visit[i][j]=0;
28         while(n--)
29         {
30             char op[2];
31             cin>>op;
32             if(op[0]=='S')
33             {
34                 node a;
35                 int l;
36                 cin>>a.x>>a.y>>l;
37                 ri(a);
38                 for(int i=a.x;i<=a.x+l;i++)
39                 for(int j=a.y;j<=a.y+l;j++)
40                 if(!visit[i][j])
41                 visit[i][j]=1;
42             }
43             else if(op[0]=='C')
44             {
45                 node a;
46                 int r;
47                 cin>>a.x>>a.y>>r;
48                 ri(a);
49                 for(int i=a.x-r;i<=a.x+r;i++)
50                 for(int j=a.y-r;j<=a.y+r;j++)
51                 if(!visit[i][j]&&(abs(a.x-i)*abs(a.x-i)+abs(a.y-j)*abs(a.y-j)<=r*r))
52                 visit[i][j]=1;
53             }
54             else
55             {//判断点是否在三角形内用到了斜面坐标系法，参考链接我会发到下面 
56                 node A,B,C,AC,AB;
57                 cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y;
58                 ri(A);ri(B);ri(C);
59                 int x1,x2,y1,y2;
60                 x1=min(A.x,min(B.x,C.x));x2=max(A.x,max(B.x,C.x));//锁定判断范围
61                 y1=min(A.y,min(B.y,C.y));y2=max(A.y,max(B.y,C.y));
62                 AC.x=C.x-A.x;AC.y=C.y-A.y;AB.x=B.x-A.x;AB.y=B.y-A.y;
63                 for(int i=x1;i<=x2;i++)
64                 for(int j=y1;j<=y2;j++)
65                 if(!visit[i][j])
66                 {
67                     node P,AP;
68                     P.x=i;P.y=j;
69                     AP.x=P.x-A.x;AP.y=P.y-A.y;
70                     int a=po(AP,AC),b=po(AB,AB),c=po(AP,AB),d=po(AC,AB),e=po(AC,AC),ans;
71                     ans=(a*b-c*d)+(c*e-a*d)-(e*b-d*d);
72                     if((a*b-c*d)>=0&&(c*e-a*d)>=0)
73                     if(ans<=0)
74                     {
75                         visit[i][j]=1;
76                     }
77                 }
78             }
79         }
80         int ans=0;
81         for(int i=0;i<250;i++)
82         for(int j=0;j<250;j++)
83         if(visit[i][j])
84         ans++;
85         cout<<ans<<endl;
86     }
87     return 0;
88 }
判断点是否在三角形内:https://www.cnblogs.com/kyokuhuang/p/4314173.html