首页 > 代码库 > 凸包,多边形面积,线段在多边形内的判定。
凸包,多边形面积,线段在多边形内的判定。
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 }
end
凸包,多边形面积,线段在多边形内的判定。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。