给出三个半平面交的裸题。
不会的上百度上谷（gu）歌（gou）一下。
毕竟学长的语文是体育老师教的。(卡格玩笑，别当真。)
这种东西明白就好，代码可以当模板。
//poj1474 Video Surveillance //点集默认顺时针 //算法参考：http://www.cnblogs.com/huangxf/p/4067763.html #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;//顺时针都是> or >=;否则都取反 for(int i=1;i<=m;i++){ if(a*q[i].x+b*q[i].y+c>=0){ // c由于精度问题，可能会偏小，所以有些点本应在右侧而没在，故应该接着判断 tmp[++tm]=q[i]; } else{ if(a*q[i-1].x+b*q[i-1].y+c>0) //如果p[i-1]在直线的右侧的话，则将p[i],p[i-1]形成的直线与已知直线的交点作为核的一个顶点 //(这样的话，由于精度的问题，核的面积可能会有所减少) 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];//将tmp中暂存的核的顶点转移到q中 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]; //读入的多边形的顶点（顺时针）、p为存放最终切割得到的多边形顶点的数组、暂存核的顶点 m=n;//m为最终切割得到的多边形的顶点数，将其初始化为多边形的顶点的个数 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 Surveillance is ",cas); puts(m?"possible. ":"impossible. "); } 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; }