给出三个半平面交的裸题。
不会的上百度上谷（gu）歌（gou）一下。
毕竟学长的语文是体育老师教的。(卡格玩笑，别当真。)
这种东西明白就好，代码可以当模板。
//poj1474 Video Surveillance //点集默认顺时针 #include<cstdio> #include<cmath> using namespace std; const int N=1e5+7; struct point{ double x,y; }p[N],tmp[N],q[N]; double a,b,c;int cas,n,m; void get_line(point p1,point p2){ a=p2.y-p1.y; b=p1.x-p2.x; c=p2.x*p1.y -p2.y*p1.x; } point cross(point p1,point p2){ double u=fabs(a*p1.x+b*p1.y+c); double v=fabs(a*p2.x+b*p2.y+c); point ret; ret.x=(v*p1.x+u*p2.x)/(u+v); ret.y=(v*p1.y+u*p2.y)/(u+v); return ret; } void cut(){ int tm=0; for(int i=1;i<=m;i++){ if(a*q[i].x+b*q[i].y+c>=0){ tmp[++tm]=q[i]; } else{ if(a*q[i-1].x+b*q[i-1].y+c>0) tmp[++tm]=cross(q[i-1],q[i]); if(a*q[i+1].x+b*q[i+1].y+c>0) tmp[++tm]=cross(q[i],q[i+1]); } } for(int i=1;i<=tm;i++) q[i]=tmp[i]; q[0]=q[tm];q[tm+1]=q[1];m=tm; } void solve(){ for(int i=1;i<=n;i++) q[i]=p[i]; q[0]=p[n];q[n+1]=q[1];p[n+1]=p[1]; m=n; for(int i=1;i<=n;i++){ get_line(p[i],p[i+1]); cut(); } } int main(){ for(cas=1;~scanf("%d",&n)&&n;cas++){ for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); solve(); printf("Floor #%d\nSurveillance is ",cas); puts(m?"possible.\n":"impossible.\n"); } return 0; }
//poj3335 Rotating Scoreboard //点集默认顺时针 #include<cstdio> #include<cmath> using namespace std; const int N=1e5+7; struct point{ double x,y; }p[N],tmp[N],q[N]; double a,b,c;int cas,n,m; void get_line(point p1,point p2){ a=p2.y-p1.y; b=p1.x-p2.x; c=p2.x*p1.y -p2.y*p1.x; } point cross(point p1,point p2){ double u=fabs(a*p1.x+b*p1.y+c); double v=fabs(a*p2.x+b*p2.y+c); point ret; ret.x=(v*p1.x+u*p2.x)/(u+v); ret.y=(v*p1.y+u*p2.y)/(u+v); return ret; } void cut(){ int tm=0; for(int i=1;i<=m;i++){ if(a*q[i].x+b*q[i].y+c>=0){ tmp[++tm]=q[i]; } else{ if(a*q[i-1].x+b*q[i-1].y+c>0) tmp[++tm]=cross(q[i-1],q[i]); if(a*q[i+1].x+b*q[i+1].y+c>0) tmp[++tm]=cross(q[i],q[i+1]); } } for(int i=1;i<=tm;i++) q[i]=tmp[i]; q[0]=q[tm];q[tm+1]=q[1];m=tm; } void solve(){ for(int i=1;i<=n;i++) q[i]=p[i]; q[0]=p[n];q[n+1]=q[1];p[n+1]=p[1]; m=n; for(int i=1;i<=n;i++){ get_line(p[i],p[i+1]); cut(); } } int main(){ for(scanf("%d",&cas);cas--;){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); solve(); puts(m?"YES":"NO"); } return 0; }
//poj3130 How I Mathematician Wonder What You Are! //点集默认逆时针 #include<cstdio> #include<cmath> using namespace std; const int N=1e5+7; struct point{ double x,y; }p[N],tmp[N],q[N]; double a,b,c;int cas,n,m; void get_line(point p1,point p2){ a=p2.y-p1.y; b=p1.x-p2.x; c=p2.x*p1.y -p2.y*p1.x; } point cross(point p1,point p2){ double u=fabs(a*p1.x+b*p1.y+c); double v=fabs(a*p2.x+b*p2.y+c); point ret; ret.x=(v*p1.x+u*p2.x)/(u+v); ret.y=(v*p1.y+u*p2.y)/(u+v); return ret; } void cut(){ int tm=0; for(int i=1;i<=m;i++){ if(a*q[i].x+b*q[i].y+c<=0){ tmp[++tm]=q[i]; } else{ if(a*q[i-1].x+b*q[i-1].y+c<0) tmp[++tm]=cross(q[i-1],q[i]); if(a*q[i+1].x+b*q[i+1].y+c<0) tmp[++tm]=cross(q[i],q[i+1]); } } for(int i=1;i<=tm;i++) q[i]=tmp[i]; q[0]=q[tm];q[tm+1]=q[1];m=tm; } void solve(){ for(int i=1;i<=n;i++) q[i]=p[i]; q[0]=p[n];q[n+1]=q[1];p[n+1]=p[1]; m=n; for(int i=1;i<=n;i++){ get_line(p[i],p[i+1]); cut(); } } int main(){ while(scanf("%d",&n)==1&&n){ for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); solve(); puts(m?"1":"0"); } return 0; }
原文：http://www.cnblogs.com/shenben/p/6285947.html