判断两个凸多边形是否相交。做比赛的时候没有判断是否两个多边形可以包含,wa!贴上去当作模板吧
1
#include<iostream>
2
#include<algorithm>
3
#include<cmath>
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
const int oo=0x7fffffff;
7
const double eps=1e-6;
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
void pass()
{cout<<"passpasspasspass"<<endl;}
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T> void print (T a)
{cout<<a<<endl;}
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T> void print (T a,int n)
{for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;}
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T> T gmax(T a,T b)
{return a>b?a:b;}
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T> T gmin(T a,T b)
{return a>b?b:a;}
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
template<class T> T square (T a)
{return a*a;}
15![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
16
const int MaxP=2005;
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18
//平面点
19
typedef struct TPoint
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
21
double x,y;
22![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
TPoint(double _x=0.0,double _y=0.0):x(_x),y(_y)
{}
23
}TPoint;
24![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
25
TPoint p0;
26
int ch[2005];
27
int top;
28![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
29
//平面直线(非方程)
30
typedef struct Line1
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
TPoint s;
33
TPoint e;
34![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
Line1(TPoint _s,TPoint _e):s(_s),e(_e)
{}
35
}Line1;
36![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
37
//平面多边形
38
typedef struct Poly
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40
TPoint p[MaxP];
41
int n;
42
}Poly;
43![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
44
//平面点的距离
45
double dist(TPoint a,TPoint b)
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
47
return square(a.x-b.x)+square(a.y-b.y);
48
}
49![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
50
//p0p1 cross p0p2
51
double cross(TPoint p0,TPoint p1,TPoint p2)
52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
53
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
54
}
55![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
//两条直线是否相交
58
bool isins(TPoint s1,TPoint e1,TPoint s2,TPoint e2)
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
70
//判断点是否在多边形内部利用面积是否相等
71
bool inpoly(TPoint p,Poly a)
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
73
int i,area1=0,area2=0;
74
a.p[a.n]=a.p[0];//把p0给pn,便于循环
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
//判断凸多边形是否相交
83
bool ins(Poly &a,Poly &b)
84![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
97
//graham扫描法求凸包
98
bool cmp(TPoint a,TPoint b)
99![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
107
void graham(TPoint p[],int n)
108![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
120
while(cross(p[ch[top-1]],p[ch[top]],p[i])<=0)
121![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
122
if(top==1)break;
123
top--;
124
}
125
ch[++top]=i;
126
}
127
}
128![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
129![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
130
TPoint p[MaxP];
131![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
132
int main()
133![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
139
for(i=0,n=0;i<D;i++)
140![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
153
for(i=0,n=0;i<P;i++)
154![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
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
}