首页 > 代码库 > 凸包,多边形面积,线段在多边形内的判定。

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

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

 

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