poj 1584 A Round Peg in a Ground Hole 点到直线的距离点是否在多边形内多边形是否为凸

给一个多边形，和一个圆形的钉子，判断多边形是否为凸多边形，若为凸多边形判断钉子能否被包含在多边形内。

判断是否为凸多边形：相邻的两条边做叉乘i*(i+1)都大于零（假定顶点为逆时针排序，顺时针反之）则为凸多边形。

判断圆心是否在多边形内：设o为圆心，s1,s2为相邻顶点，若叉乘（s1s2）*(s1o)都大于零则圆心在多边形内部。（假定顶点为逆时针排序，顺时针反之）

之后找圆心到多边形边的最短距离，若最短距离小于圆半径必定不会包含在多边形内。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<math.h>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define eps 1e-8
 8 using namespace std;
 9 struct point
10 {
11     double x,y;
12 }p[10000];
13 double multi(point p0,point p1,point p2)
14 {
15     return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
16 }
17 point inter(point u1,point u2,point v1,point v2)
18 {
19     point ret=u1;
20     double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
21         /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
22     ret.x+=(u2.x-u1.x)*t;
23     ret.y+=(u2.y-u1.y)*t;
24     return ret;
25 }
26 
27 bool is(point s1,point e1,point s2,point e2)
28 {
29     return  (max(s1.x,e1.x)>=min(s2.x,e2.x))&&
30         (max(s2.x,e2.x)>=min(s1.x,e1.x))&&
31         (max(s1.y,e1.y)>=min(s2.y,e2.y))&&
32         (max(s2.y,e2.y)>=min(s1.y,e1.y))&&
33         (multi(s1,s2,e1)*multi(s1,e1,e2)>=0)&&
34         (multi(s2,s1,e2)*multi(s2,e2,e1)>=0);
35 }
36 point pt(point p,point t1,point t2)
37 {
38     point t=p;
39     t.x+=t1.y-t2.y;
40     t.y+=t2.x-t1.x;
41     return inter(p,t,t1,t2);
42 }
43 double dis(point a,point b)
44 {
45     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
46 }
47 void work(point t,int n,double r)
48 {
49     int i;
50     double flag;
51     point a;
52     flag=multi(p[0],p[1],p[2]);//做顶点顺、逆时针标记
53     for(i=1;i<n-1;i++)
54         if(flag*multi(p[i],p[i+1],p[i+2])<-eps)
55         {
56             printf("HOLE IS ILL-FORMED\n");
57             return;
58         } 
59         for(i=0;i<n;i++)
60         {
61             a=pt(t,p[i],p[i+1]);
62             if(multi(p[i],p[i+1],t)*flag<-eps)//圆心不在多边形内部
63             {
64                 printf("PEG WILL NOT FIT\n");
65                 return;
66             }
67             if(dis(a,t)-r<-eps)
68             {
69                 printf("PEG WILL NOT FIT\n");
70                 return;
71             }
72         }
73         printf("PEG WILL FIT\n");
74 }
75 int main()
76 {
77     int i,n;
78     double r;
79     point t;
80     while(scanf("%d",&n),n>=3)
81     {
82         scanf("%lf%lf%lf",&r,&t.x,&t.y);
83         for(i=0;i<n;i++)
84             scanf("%lf%lf",&p[i].x,&p[i].y);
85         p[n]=p[0];
86         work(t,n,r);
87     }
88     return 0;
89 }

poj 1584 A Round Peg in a Ground Hole 点到直线的距离 点是否在多边形内 多边形是否为凸

poj 1584 A Round Peg in a Ground Hole 点到直线的距离点是否在多边形内多边形是否为凸