poj 1584

题意：判断一个多边形是否为凸多边形，如果不是则输出”HOLE IS ILL-FORMED“，如果是则继续判断给定的一个圆是否在该凸多边形内，如果不在输出”PEG WILL NOT FIT“，否则输出”PEG WILL FIT“；

思路：用一维数组保存给的顶点，增加两个点构成一个使得数组从0 到n + 1 构成一个环。由于给点的点是按顺时针或逆时针的，所以先算出point[0],point[1],point[2]三个点构成的两条边的叉积，作为判断标准。如果一个多边形为凸变形，那么按照一个方向枚举每两条边时叉积的符号是相同的。然后判断两条边是否在以两条边的公共点和圆心构成的直线的两侧，并且判断圆心到到两条的距离是否大于半径。

知道直线经过的两点(P1.x , p1.y) , (p2.x , p2.y)，根据两点式，该直线方程为：(p1.y - p2.y) *x + (p2.x - p1.x) * y + p2.y * p1.x - p2.x * p1.y = 0，再根据点到直线的距离公式求圆心到直线的距离。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <math.h>
 6 #define N 1000
 7 
 8 using namespace std;
 9 
10 struct node
11 {
12     double x;
13     double y;
14 };
15 node point[N];
16 int n;
17 node p;
18 double r,xr,yr;
19 double juge(node p1,node p2,node p3)
20 {
21     double x1 = p2.x - p1.x;
22     double x2 = p3.x - p2.x;
23     double y1 = p2.y - p1.y;
24     double y2 = p3.y - p2.y;
25     double temp = x1 * y2 - y1 * x2;
26     return temp;
27 }
28 double jugee(double x1,double x2,double y1,double y2)
29 {
30     double ans = x1 * y2 - x2 * y1;
31     return ans;
32 }
33 int dis(node p1,node p2)
34 {
35     double A2 = p1.y - p2.y;
36     double B2 = p2.x - p1.x;
37     double C2 = p2.y * p1.x - p2.x * p1.y;
38     double dist2 = fabs(A2 * p.x + B2 * p.y + C2) / sqrt(A2 * A2 + B2 * B2); // 距离公式
39     if(dist2 >= r) return 1;
40     else return 0;
41 }
42 int main()
43 {
44     int i;
45     //freopen("data.txt","r",stdin);
46     while(scanf("%d",&n),n >= 3)
47     {
48         scanf("%lf%lf%lf",&r,&xr,&yr);
49         p.x = xr;
50         p.y = yr;
51         for(i = 1; i <= n; i++)
52         scanf("%lf%lf",&point[i].x,&point[i].y);
53         point[0] = point[n];
54         point[n + 1] = point[1];
55         int flag = 0;
56         int temp = (juge(point[0],point[1],point[2]) < 0) ? -1:1;
57         for(i = 1; i <= n - 1; i++)
58         {
59             if(temp * juge(point[i],point[i + 1],point[i + 2]) < 0)
60             {
61                 flag = 1;break;
62             }
63         }
64         if(flag){cout<<"HOLE IS ILL-FORMED\n";continue;}
65         int mark = 0;
66         for(i = 1;i <= n; i++)
67         {
68             double x1,x2,y1,y2;
69             x1 = point[i].x - point[i - 1].x;
70             y1 = point[i].y - point[i - 1].y;
71             x2 = point[i].x - p.x;
72             y2 = point[i].y - p.y;
73             double temp = jugee(x1,x2,y1,y2);
74             x1 = point[i].x - point[i + 1].x;
75             y1 = point[i].y - point[i + 1].y;
76             x2 = point[i].x - p.x;
77             y2 = point[i].y - p.y;
78             double kemp = jugee(x1,x2,y1,y2);  
79             if(temp * kemp > 0) // 如果两条边在直线的同侧，那么他们的叉积符号相同
80             {
81                 flag = 1;
82                 break;
83             }
84             if(!dis(point[i - 1],point[i]))
85             {
86                 mark = 1;
87                 break;
88             }
89         }
90         if(flag || mark) cout<<"PEG WILL NOT FIT\n";
91         else cout<<"PEG WILL FIT\n";
92     }
93     return 0;
94 }