凸包，多边形面积，线段在多边形内的判定。

zoj3570 Lott's Seal http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4569
  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cmath>
  4 #include<algorithm>
  5 using namespace std;
  6 const double eps=1e-8;
  7 const int M=100010;
  8 struct point{
  9     double x,y;
 10 }p[M],q[M],res[M];
 11 bool operator < (const point &l, const point &r) {
 12     return l.y < r.y || (fabs(l.y- r.y)<eps && l.x < r.x);
 13 }
 14 class ConvexHull { //凸包
 15     bool mult(point sp, point ep, point op) {//>包括凸包边上的点,>=不包括
 16         return (sp.x - op.x) * (ep.y - op.y)>= (ep.x - op.x) * (sp.y - op.y);
 17     }
 18 public:
 19     int graham(int n,point p[],point res[]) {//多边形点个数和点数组，凸包存res
 20         sort(p, p + n);
 21         if (n == 0) return 0;
 22         res[0] = p[0];
 23         if (n == 1) return 1;
 24         res[1] = p[1];
 25         if (n == 2) return 2;
 26         res[2] = p[2];
 27         int top=1;
 28         for (int i = 2; i < n; i++) {
 29             while (top && mult(p[i], res[top], res[top-1])) top--;
 30             res[++top] = p[i];
 31         }
 32         int len = top;
 33         res[++top] = p[n - 2];
 34         for (int i = n - 3; i >= 0; i--) {
 35             while (top!=len && mult(p[i], res[top],res[top-1])) top--;
 36             res[++top] = p[i];
 37         }
 38         return top; // 返回凸包中点的个数
 39     }
 40 } tubao;
 41 class PolygonJudge { //任意多边形判定
 42 #define zero(x) (((x)>0?(x):-(x))<eps)
 43     double xmult(point p1,point p2,point p0) {
 44         return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 45     }
 46     inline int opposite_side(point p1,point p2,point l1,point l2) {
 47         return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;
 48     }
 49     inline int dot_online_in(point p,point l1,point l2) {
 50         return zero(xmult(p,l1,l2))&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps;
 51     }
 52 public:
 53     int inside_polygon(point q,int n,point p[],int on_edge=1) {//判点在任意多边形内,顶点按顺时针或逆时针给出
 54         point q2;
 55         const int offset=120000;//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限
 56         int i=0,cnt;
 57         while (i<n)
 58             for (cnt=i=0,q2.x=rand()+offset,q2.y=rand()+offset; i<n; i++)
 59                 if(zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps) return on_edge;
 60                 else if (zero(xmult(q,q2,p[i]))) break;
 61                 else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps) cnt++;
 62         return cnt&1;
 63     }
 64     //判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1（有一个定点或两个定点在边界上，用此函时需用点在多边形内的函数）
 65     int inside_polygon(point l1,point l2,int n,point* p) {
 66         point t[M],tt;
 67         int i,j,k=0;
 68         if (!inside_polygon(l1,n,p)||!inside_polygon(l2,n,p)) return 0;
 69         for (i=0; i<n; i++)
 70             if (opposite_side(l1,l2,p[i],p[(i+1)%n])&&opposite_side(p[i],p[(i+1)%n],l1,l2)) return 0;
 71             else if (dot_online_in(l1,p[i],p[(i+1)%n])) t[k++]=l1;
 72             else if (dot_online_in(l2,p[i],p[(i+1)%n])) t[k++]=l2;
 73             else if (dot_online_in(p[i],l1,l2)) t[k++]=p[i];
 74         for (i=0; i<k; i++)
 75             for (j=i+1; j<k; j++) {
 76                 tt.x=(t[i].x+t[j].x)/2;
 77                 tt.y=(t[i].y+t[j].y)/2;
 78                 if (!inside_polygon(tt,n,p)) return 0;
 79             }
 80         return 1;
 81     }
 82 } gx;
 83 class Area { //面积
 84     double xmult(point p1,point p2,point p0) {//计算cross product (P1-P0)x(P2-P0)
 85         return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
 86     }
 87     double xmult(double x1,double y1,double x2,double y2,double x0,double y0) {
 88         return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
 89     }
 90 public:
 91     double area_triangle(point p1,point p2,point p3) {//计算三角形面积,输入三顶点
 92         return fabs(xmult(p1,p2,p3))/2;
 93     }
 94     double area_triangle(double x1,double y1,double x2,double y2,double x3,double y3) {
 95         return fabs(xmult(x1,y1,x2,y2,x3,y3))/2;
 96     }
 97     double area_triangle(double a,double b,double c) {//计算三角形面积,输入三边长
 98         double s=(a+b+c)/2;
 99         return sqrt(s*(s-a)*(s-b)*(s-c));
100     }
101     double area_polygon(int n,point p[]) {//计算多边形面积,顶点按顺时针或逆时针给出
102         double s1=0,s2=0;
103         for (int i=0; i<n; i++){
104             s1+=p[(i+1)%n].y*p[i].x;
105             s2+=p[(i+1)%n].y*p[(i+2)%n].x;
106         }
107         return fabs(s1-s2)/2;
108     }
109 } area;
110 int main(){
111     double X,Y,R,S;
112     int n=12,m;
113     while(~scanf("%lf%lf",&X,&Y)){
114         scanf("%d",&m);
115         for(int i=0;i<m;i++){
116             scanf("%lf%lf",&q[i].x,&q[i].y);
117         }
118         scanf("%lf%lf",&R,&S);
119         for(int i=0;i<6;i++){
120             p[i].x=X;
121             p[i].y=Y;
122         }
123         double tmp=R*sqrt(3.0)/2;
124         p[0].x+=R;
125         p[0].y+=0;
126         p[1].x+=R+R/2;
127         p[1].y+=tmp;
128         p[2].x+=R/2;
129         p[2].y+=tmp;
130         p[3].x+=0;
131         p[3].y+=tmp*2;
132         p[4].x+=-R/2;
133         p[4].y+=tmp;
134         p[5].x+=-R-R/2;
135         p[5].y+=tmp;
136         for(int i=6;i<n;i++){
137             p[i].x=2*X-p[i-6].x;
138             p[i].y=2*Y-p[i-6].y;
139         }
140         m=tubao.graham(m,q,res);
141         res[m]=res[0];
142         bool flag=true;
143         for(int i=0;i<m;i++){
144             if(!gx.inside_polygon(res[i],res[i+1],n,p)){
145                 flag=false;
146                 break;
147             }
148         }
149         if(flag){
150             double six=area.area_polygon(n,p);
151             double in=area.area_polygon(m,res);
152             if(six-in>S+eps){
153                 puts("Succeeded.");
154                 continue;
155             }
156         }
157         puts("Failed.");
158     }
159     return 0;
160 }
View Code
end