判斷兩個凸多邊形是否相交。做比賽的時候沒有判斷是否兩個多邊形可以包含，wa！貼上去當(dāng)作模板吧
1
#include<iostream>
2#include<algorithm>
3#include<cmath>
4using namespace std;
5
6const int oo=0x7fffffff;
7const double eps=1e-6;
8
9
void pass() 
{cout<<"passpasspasspass"<<endl;}
10template<class T> void print (T a) {cout<<a<<endl;}
11template<class T> void print (T a,int n) {for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;}
12template<class T> T gmax(T a,T b) {return a>b?a:b;}
13template<class T> T gmin(T a,T b) {return a>b?b:a;}
14template<class T> T square (T a) {return a*a;}
15
16const int MaxP=2005;
17
18//平面點
19typedef struct TPoint
20{
21
double x,y;
22
TPoint(double _x=0.0,double _y=0.0):x(_x),y(_y){}
23
}TPoint;
24
25TPoint p0;
26int ch[2005];
27int top;
28
29//平面直線(非方程)
30typedef struct Line1
31{
32 TPoint s;
33 TPoint e;
34 Line1(TPoint _s,TPoint _e):s(_s),e(_e){}
35}Line1;
36
37//平面多邊形
38typedef struct Poly
39{
40 TPoint p[MaxP];
41 int n;
42}Poly;
43
44//平面點的距離
45double dist(TPoint a,TPoint b)
46{
47 return square(a.x-b.x)+square(a.y-b.y);
48}
49
50//p0p1 cross p0p2
51double cross(TPoint p0,TPoint p1,TPoint p2)
52{
53 return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
54}
55
56
57//兩條直線是否相交
58bool isins(TPoint s1,TPoint e1,TPoint s2,TPoint e2)
59{
60 if(gmax(s1.x,e1.x)>=gmin(s2.x,e2.x)&&
61 gmax(s2.x,e2.x)>=gmin(s1.x,e1.x)&&
62 gmax(s1.y,e1.y)>=gmin(s2.y,e2.y)&&
63 gmax(s2.y,e2.y)>=gmin(s1.y,e1.y)&&
64 cross(s1,s2,e1)*cross(s1,e1,e2)>=0&&
65 cross(s2,s1,e2)*cross(s2,e2,e1)>=0)
66 return true;
67 else return false;
68}
69
70//判斷點是否在多邊形內(nèi)部利用面積是否相等
71bool inpoly(TPoint p,Poly a)
72{
73 int i,area1=0,area2=0;
74 a.p[a.n]=a.p[0];//把p0給pn，便于循環(huán)
75 for(i=0;i<a.n;i++)
76 area1+=fabs(cross(p,a.p[i],a.p[i+1]));
77 for(i=1;i<a.n-1;i++)
78 area2+=fabs(cross(a.p[0],a.p[i],a.p[i+1]));
79 if(fabs(area1-area2)<eps)return true;
80 else return false;
81}
82//判斷凸多邊形是否相交
83bool ins(Poly &a,Poly &b)
84{
85 a.p[a.n]=a.p[0];
86 b.p[b.n]=b.p[0];
87 int i,j;
88 for(i=0;i<a.n;i++)
89 for(j=0;j<b.n;j++)
90 if(isins(a.p[i],a.p[i+1],b.p[j],b.p[j+1]))
91 return true;
92 if(inpoly(a.p[0],b)||inpoly(b.p[0],a))
93 return true;
94 return false;
95}
96
97//graham掃描法求凸包
98bool cmp(TPoint a,TPoint b)
99{
100 double c=cross(p0,a,b);
101 if(c>0)return true;
102 else if(!c&&dist(p0,b)<dist(p0,a))
103 return true;
104 else return false;
105}
106
107void graham(TPoint p[],int n)
108{
109 int i,se=0;
110 for(i=0;i<n;i++)
111 if(p[i].y<p[se].y||(p[i].y==p[se].y&&p[i].x<p[se].x))
112 se=i;
113 swap(p[se],p[0]);
114 p0=p[0];
115 sort(p+1,p+n,cmp);
116 for(i=0;i<=1;i++) ch[i]=i;
117 top=1;
118 for(i=2;i<n;i++)
119 {
120 while(cross(p[ch[top-1]],p[ch[top]],p[i])<=0)
121 {
122 if(top==1)break;
123 top--;
124
}
125 ch[++top]=i;
126 }
127}
128
129
130TPoint p[MaxP];
131
132int main()
133{
134 int T=1,i,n;
135 double X1,Y1,X2,Y2;
136 int D,P;
137 while(scanf("%d%d",&D,&P)&&(D||P))
138 {
139 for(i=0,n=0;i<D;i++)
140 {
141 scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
142 p[n].x=X1; p[n++].y=Y1;
143 p[n].x=X2; p[n++].y=Y1;
144 p[n].x=X2; p[n++].y=Y2;
145 p[n].x=X1; p[n++].y=Y2;
146 }
147 Poly d;
148 graham(p,n);
149 for(i=0;i<=top;i++)
150 d.p[i]=p[ch[i]];
151 d.n=top+1;
152
153 for(i=0,n=0;i<P;i++)
154 {
155 scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
156 p[n].x=X1; p[n++].y=Y1;
157 p[n].x=X2; p[n++].y=Y1;
158 p[n].x=X2; p[n++].y=Y2;
159 p[n].x=X1; p[n++].y=Y2;
160 }
161 Poly pe;
162 graham(p,n);
163 for(i=0;i<=top;i++)
164 pe.p[i]=p[ch[i]];
165 pe.n=top+1;
166
167 if(ins(d,pe))
168 printf("Case %d: It is not possible to separate the two groups of vendors.\n\n",T++);
169 else
170 printf("Case %d: It is possible to separate the two groups of vendors.\n\n",T++);
171 }
172 return 0;
173}