半平面交（入门）

首先解决问题：什么是半平面？ 顾名思义，半平面就是指平面的一半，我们知道，一条直线可以将平面分为两个部分，那么这两个部分就叫做两个半平面。

然后，半平面怎么表示呢？ 二维坐标系下，直线可以表示为ax + by + c = 0，那么两个半平面则可以表示为ax + by + c >= 0 和ax + by + c < 0，这就是半平面的表示方法。

那么，半平面交是啥呢？按字面意思就是，n个平面的相交。

首先，看一道入门题：

题目描述

【题意】 在一个有限大（-10 0000<=x,y<=10 0000)的平面坐标系上有n个半平面（注意有限的），每个半平面给出一条有向线段（x1,y1)——>(x2,y2）。 每个半平面的有效区域都是左侧。求这n个半平面的交的面积。 【输入文件】 第一行一个整数n（1 <= n <= 2 0000） 下来n个半平面。每个半平面一行四个整数x1,y1,x2,y2。（-100000 <= x1,y1,x2,y2 <= 100000) 【输出文件】 一行，输出n个半平面的交的面积（保留一位小数），如果有效面积不存在则输出"0.0"。 【样例1输入】 3 1 1  9 9 5 10  4 10 0 3 0 2 【样例1输出】 50.0 【样例2输入】 4 0 0  10 0 10 0  10 10 10 10 0 10 11 11 11 0 【样例2输出】 0.0

也没啥好说的，模代码吧：推荐一篇blog，有助于理解代码

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #define eps 1e-8 const int N=21000; using namespace std; double Maxx=100000.0; double Minn=-100000.0; int n; struct node{ double x,y; }sb[N];int pl=0; struct node2{ node p1,p2; double angle; node2(){} node2(double x1,double y1,double x2,double y2) { p1.x=x1;p1.y=y1;p2.x=x2;p2.y=y2; } void get_angle() { angle=atan2(p2.y-p1.y,p2.x-p1.x); } }seg[N],sa[N];int st,ed; double mulit(node p1,node p2,node p0) { double x1=p1.x-p0.x,y1=p1.y-p0.y; double x2=p2.x-p0.x,y2=p2.y-p0.y; return x1*y2-x2*y1; }//求叉积 bool satify(node x,node2 y)//判断点x是否在平面y上 { if(mulit(x,y.p2,y.p1)<=eps) return true;return false; } bool cmp(node2 x,node2 y)//根据极角排序 { if(x.angle<y.angle) return true; if(fabs(x.angle-y.angle)<eps&&satify(x.p1,y)==true) return true; return false; } node jd(node2 x,node2 y)//求两个平面的交点 { node p1=x.p1,p2=x.p2,p3=y.p1,p4=y.p2,p; double t1=mulit(p1,p4,p3); double t2=mulit(p2,p4,p3); p.x=(t1*p2.x-t2*p1.x)/(t1-t2); p.y=(t1*p2.y-t2*p1.y)/(t1-t2); return p; } void work() { sort(seg+1,seg+n+1,cmp); int tp=1; for(int i=2;i<=n;i++) if(seg[i].angle-seg[tp].angle>eps) seg[++tp]=seg[i]; n=tp; sa[1]=seg[1];sa[2]=seg[2]; st=1,ed=2; for(int i=3;i<=n;i++) { while(st<ed&&satify(jd(sa[ed],sa[ed-1]),seg[i])==false) ed--; while(st<ed&&satify(jd(sa[st],sa[st+1]),seg[i])==false) st++; sa[++ed]=seg[i]; } while(st<ed&&satify(jd(sa[ed],sa[ed-1]),seg[st])==false) ed--; while(st<ed&&satify(jd(sa[st],sa[st+1]),seg[ed])==false) st++; if(ed-st+1<=2){printf("0.0");return;} pl=0; for(int i=st;i<ed;i++) sb[++pl]=jd(sa[i],sa[i+1]); sb[++pl]=jd(sa[ed],sa[st]); double ans=0.0; for(int i=3;i<=pl;i++) ans+=mulit(sb[i-1],sb[i],sb[1]); printf("%0.1lf",fabs(ans)/2.0); } int main() { scanf("%d",&n); double x1,x2,y1,y2; for(int i=1;i<=n;i++) { scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); seg[i]=node2(x1,y1,x2,y2); seg[i].get_angle(); } work(); }