这次讲半平面交。应该是平面几何基础算法的最后一节了（凸包，旋转卡壳，半平面交）。 说几句题外话，这些算法都比较耐（keng）用（die），比如凸包好像可以用于来优化DP（好像是利用斜率），很多模型都可以用旋转卡壳往上套，而半平面交……可以处理许多与平面几何没有半毛钱关系的题目，尤其是对于一些不等式组的解集的存在，但是菜鸡fhj现在只会用模板解决单纯的半平面交的问题。
首先要先定义有向直线，那么它所对应的半平面就是其有向直线的左半边。而半平面交就是若干个半平面的公共部分，先给出定义：
//有向线段的定义，它的左边就是半平面 struct hdata{ fdata p,v; double ang; // p为点，v为向量，ang表示极角 hdata (){} //初始化，否则会发生错误 hdata (fdata pi,fdata vi) {p=pi;v=vi;ang=atan2(v.y,v.x);} //方便赋值 bool operator < (const hdata& b) const{ return ang<b.ang; } }然后，就直接开始写半平面交了，在这里我们用一种类似于求凸包的方法解决半平面交，不过并不是用栈，而是用双端队列。首先对所有有向直线排序，然后依次加入各个半平面。注意因为已经用极角排序，所以每次新加入的有向直线会让之前的有向直线的半平面无用，从而删除。 还有，不知是反三角函数的奇特性，新加的半平面也可能绕了一圈，最后让队首的半平面变得无用，所以这就是要用双端队列的原因。
其实，就这样了，无法再BB下去了。
例题如下，求半平面的交的面积。 poj 1279
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct fdata{ double x,y; fdata (double x=0,double y=0):x(x),y(y){} }ch[1505],p[1505]; struct hdata{ fdata p,v; double ang; hdata (){} hdata (fdata pi,fdata vi){p=pi;v=vi;ang=atan2(v.y,v.x);} bool operator < (const hdata& b) const{ return ang<b.ang; } }lne[1505],que[1505]; int n,tst,m; double ans; fdata operator + (const fdata a,const fdata b) {return fdata(a.x+b.x,a.y+b.y);} fdata operator - (const fdata a,const fdata b) {return fdata(a.x-b.x,a.y-b.y);} fdata operator * (const fdata a,const double b) {return fdata(a.x*b,a.y*b);} double cross(fdata a,fdata b) {return a.y*b.x-a.x*b.y;} double getS(fdata a,fdata b,fdata c) {return cross(b-a,c-a);} bool pd_lft(fdata p,hdata L) //判断点是否在有向线段左边 { return cross(L.v,p-L.p)>0; } fdata getJ(hdata a,hdata b) //求两直线交点 { fdata u=a.p-b.p; double t=cross(b.v,u)/cross(a.v,b.v); return a.p+a.v*t; } void _init() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lf%lf",&ch[i].x,&ch[i].y); ch[n+1]=ch[1]; for (int i=n+1;i>1;i--) lne[n-i+2]=hdata(ch[i],ch[i]-ch[i-1]); } double getTS() //求半平面的交的面积 { double tem=0; for (int i=2;i<m;i++) tem+=cross(p[i+1]-p[1],p[i]-p[1]); return tem/2; } void _solve() //主程序，求半平面交 { sort(lne+1,lne+n+1); int hed=1,til=1; que[1]=lne[1]; for (int i=2;i<=n;i++) { while (hed<til&&!pd_lft(p[til-1],lne[i])) til--; while (hed<til&&!pd_lft(p[hed],lne[i])) hed++; que[++til]=lne[i]; if (fabs(cross(que[til].v,que[til-1].v))<1e-6) { til--; if (pd_lft(lne[i].p,que[til])) que[til]=lne[i]; } //极角相同的，保留在里面的 if (hed<til) p[til-1]=getJ(que[til-1],que[til]); } while (hed<til&&!pd_lft(p[til-1],que[hed])) til--; if (til-hed<=1) {printf("0.00\n"); return;} p[til]=getJ(que[til],que[hed]); m=til-hed+1; printf("%0.2lf\n",getTS()); } int main() { scanf("%d",&tst); while (tst--) { _init(); _solve(); } return 0; }