题目地址：http://poj.org/problem?id=1474
半平面交的典型题目，模板直接上，但要注意题目中点的方向是顺时针给出的，要变为逆时针
以下为联机算法代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define Vector Point
const double EPS=1e-6;
int Sign(double x){ if(fabs(x)<EPS) return 0;return x<0?-1:1;
}
struct Point{double x,y;Point(double x,double y):x(x),y(y){}Vector operator - (const Point& p){return Vector(x-p.x,y-p.y);}double operator * (const Vector& v){return x*v.x+y*v.y;}
};
double cross(const Point& a,const Point& b){return a.x*b.y-a.y*b.x;
}
Vector operator * (double k,Vector p){ //c=f*|a|;return Vector(k*p.x,k*p.y);
}
Vector operator + (Point a,Vector b){return Vector(a.x+b.x,a.y+b.y);
}
bool operator == (Point a,Point b){return Sign(a.x-b.x)==0&&Sign(a.y-b.y)==0;
}
struct Seg{Point a,b;Seg(const Point& a,const Point& b):a(a),b(b){}
}; typedef vector<Point> Polygon;//两条线段相交的各种情况
//结果保存在pair<int,Point> 中
//返回值 result.first:
//0 规范相交，
//1 端点重合，但不平行，不共线
//2 一个端点在另一个内部 s1端点在 s2内部 (不平行，不共线）
//3 一个端点在另一个内部 s2端点在 s1内部 (不平行，不共线）
//4 无交点，不平行，不共线，两直线交点是result.second
//5 平行
//6 共线且有公共点
//7 共线且无公共点
//8 s1,s2无交点，但是s2所在直线和s1有交点，即交点在s1上
//9 s1,s2无交点，但是s1所在直线和s2有交点，即交点在s2上
bool FLessEq(double a,double b){ //b不小于a return Sign(b-a)>=0;
}
double length(Vector p){ //求|p| return sqrt(p*p);
}
double dist(Point p,Seg s){return fabs(cross(p-s.a,s.b-s.a))/length(s.b-s.a); //面积除以高
}
bool PointInSeg(Point p,Seg L){ //p点在线段l内 double tmp = cross(L.a-p,L.a-L.b);if(Sign(tmp)) return false;if(FLessEq(min(L.a.x,L.b.x),p.x) &&FLessEq(p.x,max(L.a.x,L.b.x)) &&FLessEq(min(L.a.y,L.b.y),p.y) &&FLessEq(p.y,max(L.a.y,L.b.y)) )return true;return false;
}
pair<int,Point> CrossPoint(Seg s1,Seg s2){Point p1=s1.a;Point p2=s1.b;Point p3=s2.a;Point p4=s2.b;double a1 = cross(p3-p1,p4-p1); double a2 = cross(p4-p2,p3-p2);if(Sign(cross(p2-p1,p3-p1))*Sign(cross(p2-p1,p4-p1)) < 0&& Sign(cross(p4-p3,p1-p3))*Sign(cross(p4-p3,p2-p3)) < 0)return make_pair(0,p1+(a1/(a1+a2))*(p2-p1)); //规范相交if(Sign(cross(p2-p1,p3-p4))){ //不平行不共线if(p1==p3||p1==p4) return make_pair(1,p1);if(p2==p3||p2==p4) return make_pair(1,p2);if(PointInSeg(p1,s2)) return make_pair(2,p1);if(PointInSeg(p2,s2)) return make_pair(2,p2);if(PointInSeg(p3,s1)) return make_pair(3,p3);if(PointInSeg(p4,s1)) return make_pair(3,p4);Point crossPoint = p1+(a1/(a1+a2))*(p2-p1); //交点 if(PointInSeg(crossPoint,s1)) return make_pair(8,crossPoint);if(PointInSeg(crossPoint,s2)) return make_pair(9,crossPoint);//直线和线段也无交点 不平行 不共线 两直线交点是second return make_pair(4,crossPoint); } if(Sign(dist(p1,s2))) return make_pair(5,Point(0,0)); //平行//共线 且有公共点 if(PointInSeg(p1,s2)) return make_pair(6,p1);if(PointInSeg(p2,s2)) return make_pair(6,p2);if(PointInSeg(p3,s1)) return make_pair(6,p3);if(PointInSeg(p4,s1)) return make_pair(6,p4);return make_pair(7,Point(0,0));//共线 且无公共点
}int CutPloygon(Point a,Point b,const Polygon& src,Polygon& result)
{//直线a->b,切割src，返回其左边的多边形，放到result中 int n=src.size(); //src中的点并不需要排序 result.clear();for(int i=0;i<n;i++){Point c=src[i]; //取出相邻的两个点 Point d=src[(i+1)%n];if(Sign(cross(b-a,c-a))>=0) //c点在a->b左侧或上面 result.push_back(c);pair<int,Point> r=CrossPoint(Seg(c,d),Seg(a,b));if(r.first==0||r.first==8||r.first==3) result.push_back(r.second); //相交的话把交点放入}} Polygon s,r,points;int main(){int n,kase=0;while(scanf("%d",&n)&&n){points.clear();for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);points.push_back(Point(x,y));}s=points;for(int i=n-1;i>=0;i--){Point a=points[(i+1)%n],b=points[i];CutPloygon(a,b,s,r);s=r;if(s.size()==0) break;}printf("Floor #%d\n%s\n\n",++kase,r.size()?"Surveillance is possible.":"Surveillance is impossible.");}return 0;}