首页 > 代码库 > POJ 2451-半平面交
POJ 2451-半平面交
半平面交第一次真的好难写啊。。前后加起来起码弄了7小时。
半平面交的算法思想并不复杂：
1、将所有向量按极角大小从小到大排序，向量(x,y)的极角=atan2(y,x)，当两个向量的极角相等时选择性的保留在较左边的那个
2、运用一种数据结构：双端队列，用phead表示双端队列的头位置，pend表示双端队列的尾位置，初始化时phead=0，pend=-1
然后开始一个一个添加已经排好序的向量进双端队列中：
设当前要添加的向量是v
#当双端队列中的向量数量大于等于2时（pend-phead>=1) 并且 双端队列最尾部的两个向量的交点在向量v所表示的半平面外，删除位于双端队列最尾部的那个向量（pend--)
#当双端队列中的向量数量大于等于2时 并且 双端队列最头部的两个向量的交点在向量v所表示的半平面外，删除位于双端队列最头部的那个向量（phead++）
进行外上面两个步骤后，添加当前向量v到双端队列的尾部
3、当排好序的向量全部添加完之后，还需要一次判定，过程和上一步类似：
#当双端队列中的向量数量大于2时，如果双端队列尾部的两个向量的交点在 最头部的向量所表示的半平面外，删除位于双端队列最尾部的那个向量
#当双端队列中的向量数量大于2时，如果双端队列头部的两个向量的交点在 最尾部的向量所表示的半平面外，删除位于双端队列最头部的那个向量
4、依次求双端队列相邻两个向量的交点 即为 所有半平面的交围成的凸多边形的顶点（当然也有可能是非封闭图形或者线段、点，甚至是空集）
有一个非常重要的地方一定要注意：
每次一定要先判断双端队列最尾部的向量该不该删，再判断双端队列头部的向量该不该删。因为双端队列中的向量的极角是从小到大有序的，当新插入一个向量v时，应该先考虑与向量v的极角最相近的向量该不该删。
贴一个自己的半平面交的模板：（POJ2451标程）
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #define maxn 20005 7 #define EPS 1e-10 8 using namespace std; 9 int n,sum; 10 int phead=0,pend=-1; 11 struct Point{double x,y;}; 12 13 struct VecLine{ 14 double x0,y0,vx,vy; //(x0,y0)表示该向量上的一点，(vx,vy)表示该向量的方向 15 double angle; 16 friend bool operator<(const VecLine a,const VecLine b){ 17 if(fabs(a.angle-b.angle)<=EPS){ 18 double x1=a.vx,y1=a.vy; 19 double x2=b.x0-a.x0,y2=b.y0-a.y0; 20 return (x1*y2-x2*y1<0); 21 } 22 return a.angle<b.angle; 23 } 24 }line[maxn],deque[maxn]; 25 26 void AddVecLine(double x0,double y0,double vx,double vy){ 27 line[sum++]=((VecLine){x0,y0,vx,vy,atan2(vy,vx)}); 28 } 29 void init(){ 30 scanf("%d",&n); 31 double x1,x2,y1,y2; 32 for(int i=0;i<n;i++){ 33 scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); 34 AddVecLine(x1,y1,x2-x1,y2-y1); 35 } 36 AddVecLine(0,0,10000,0); 37 AddVecLine(10000,0,0,10000); 38 AddVecLine(10000,10000,-10000,0); 39 AddVecLine(0,10000,0,-10000); 40 41 sort(line,line+sum); 42 int tot=0; 43 for(int i=1;i<sum;i++){ 44 if(fabs(line[i].angle-line[tot].angle)>EPS) line[++tot]=line[i]; 45 46 } 47 sum=++tot; 48 49 } 50 Point Get_cross_point(VecLine A,VecLine B){ 51 double x0=A.x0,y0=A.y0,x1=A.vx,y1=A.vy; 52 double x2=B.x0,y2=B.y0,x3=B.vx,y3=B.vy; 53 double k=(y2*x1+y1*x0-x1*y0-y1*x2)/(x3*y1-y3*x1); 54 double x=x2+k*x3,y=y2+k*y3; 55 return ((Point){x,y}); 56 } 57 58 bool Judge(VecLine A,VecLine B,VecLine C){//Judge函数用于判断向量A和向量B的交点是否在向量C的左侧 59 Point p=Get_cross_point(A,B); 60 p.x=p.x-C.x0;p.y=p.y-C.y0; 61 return (p.x*C.vy-p.y*C.vx<0); 62 } 63 64 void Get_Half_Plane(){ 65 for(int i=0;i<sum;i++){ 66 VecLine X=line[i]; 67 while((pend-phead)>=1 && !Judge(deque[pend],deque[pend-1],X)) pend--; 68 while((pend-phead)>=1 && !Judge(deque[phead],deque[phead+1],X)) phead++; 69 pend++;deque[pend]=X; 70 } 71 while((pend-phead)>=2 && !Judge(deque[pend],deque[pend-1],deque[phead])) pend--; 72 while((pend-phead)>=2 && !Judge(deque[phead],deque[phead+1],deque[pend])) phead++; 73 } 74 void GetArea(){ 75 double S=0; 76 Point ans[maxn]; 77 int t=0; 78 for(int i=phead;i<=pend;i++){ 79 int j=i+1;if (j>pend) j=phead; 80 ans[t++]=Get_cross_point(deque[i],deque[j]); 81 82 } 83 ans[t]=ans[0]; 84 for(int i=0;i<t;i++){ 85 S+=(ans[i].x*ans[i+1].y-ans[i+1].x*ans[i].y); 86 } 87 S=fabs(S/2); 88 printf("%.1f\n",S); 89 } 90 91 92 int main(){ 93 init(); //读入数据，并添加到存向量的数组，并按极角排序 94 Get_Half_Plane(); //求出半平面交 95 GetArea(); //计算面积 96 return 0; 97 }
POJ 2451-半平面交