POJ1584A Round Peg in a Ground Hole

转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1309142308

大致题意：

按照顺时针或逆时针方向输入一个n边形的顶点坐标集，先判断这个n边形是否为凸包。

再给定一个圆形（圆心坐标和半径），判断这个圆是否完全在n变形内部。

解题思路：

题意已经很直白了。。就是那个思路。。。

注意输入完顶点集后，要封闭多边形，方便后面枚举边。

封闭方法：

定义点集数组Vectex[1~n]记录n个顶点，再令Vectex[0]=Vectex[n]，Vectex[n+1]=Vectex[1]

1、判断凸包：

由于点集已经按某个时针方向有序，因此可以先定义一个方向系数direction=0

两两枚举n边形的边，用叉积判断这两条边的转向（右螺旋或左螺旋），由于存在散点共线的情况，因此当且仅当叉积的值temp第一次不为0时，direction=temp，direction的值此后不再改变。（direction>0 则为右螺旋逆时针，direction<0则为左螺旋顺时针）

此后继续枚举剩下的边，只要判断direction*temp>=0即可，当存在一个direction*temp<0的边，说明这是凹多边形，就不是凸包了。

2、判断圆心与多边形的关系：

用环顾法：

设圆心为P，逐条枚举n边形的边AB，利用

计算PA和PB的夹角，最后求和得到的就是环顾角。

（1）圆心在多边形内部时，环顾角=±360

（2）圆心在多边形外部时，环顾角=0

（3）圆心在多边形边上时（不包括顶点），环顾角=±180

（4）圆心在多边形顶点时，环顾角为(0,360)之间的任意角，其实就是圆心所在的顶点的两条邻接边的夹角。

3、当圆心在圆内时，判断圆与多边形的关系

设圆心为P，逐条枚举n边形的边AB，利用得到△PAB的面积，

再根据公式S=0.5*|AB|*h，可以得到

枚举所有h与圆的半径R比对，只要所有的边都有R-h>=0，则说明圆在多边形内

Source修正：

把原题的“Mid-Atlantic 2003”修正为以下黑斜体内容，可用于找到本题的测试数据

谷歌搜索：

Index of /archive/2003/problems/MidAtlantic-2003

http://midatl.fireduck.com/archive/2003/problems/

  1 //Memory Time
  2 //268K    0MS 
  3 
  4 #include<iostream>
  5 #include<cmath>
  6 using namespace std;
  7 
  8 const double eps=1e-6;
  9 const double pi=3.141592654;
 10 
 11 typedef class NODE
 12 {
 13     public:
 14         double x,y;
 15 }pos;
 16 
 17 int n;
 18 double PegR;  //钉子半径
 19 pos Peg;  //钉子坐标
 20 
 21 int precision(double x);  //精度讨论
 22 double det(double x1,double y1,double x2,double y2);  //叉积
 23 double dotdet(double x1,double y1,double x2,double y2);  //点积
 24 double cross(pos A,pos B,pos C,pos D);
 25 double distant(pos A,pos B);  //计算距离
 26 double angle(pos A,pos B,pos P);  //计算向量PA与PB夹角
 27 
 28 bool IsConvexBag(pos* Vectex);  //判断输入的点集是否为凸包(本题保证了输入的点集为按某一时针方向有序)
 29 bool IsIn(pos* Vectex); //判断圆心是否在多边形内部
 30 bool IsFit(pos* Vectex);  //判断圆的半径是否<=其圆心到多边形所有边的最小距离
 31 
 32 int main(void)
 33 {
 34     while(cin>>n && n>=3)
 35     {
 36         cin>>PegR>>Peg.x>>Peg.y;
 37         pos* Vectex=new pos[n+2];  //多边形顶点坐标
 38 
 39         for(int i=1;i<=n;i++)
 40             cin>>Vectex[i].x>>Vectex[i].y;
 41 
 42         Vectex[0].x=Vectex[n].x;  //封闭多边形
 43         Vectex[0].y=Vectex[n].y;
 44         Vectex[n+1].x=Vectex[1].x;
 45         Vectex[n+1].y=Vectex[1].y;
 46 
 47         if(!IsConvexBag(Vectex))
 48             cout<<"HOLE IS ILL-FORMED"<<endl;
 49         else
 50         {
 51             bool flag1=IsIn(Vectex);
 52             bool flag2=IsFit(Vectex);
 53 
 54             if(flag1 && flag2)
 55                 cout<<"PEG WILL FIT"<<endl;
 56             else
 57                 cout<<"PEG WILL NOT FIT"<<endl;
 58         }
 59 
 60         delete Vectex;
 61     }
 62     return 0;
 63 }
 64 
 65 /*精度讨论*/
 66 int precision(double x)
 67 {
 68     if(fabs(x)<=eps)
 69         return 0;
 70     return x>0?1:-1;
 71 }
 72 
 73 /*计算点积*/
 74 double dotdet(double x1,double y1,double x2,double y2)
 75 {
 76     return x1*x2+y1*y2;
 77 }
 78 
 79 /*计算叉积*/
 80 double det(double x1,double y1,double x2,double y2)
 81 {
 82     return x1*y2-x2*y1;
 83 }
 84 double cross(pos A,pos B,pos C,pos D)
 85 {
 86     return det(B.x-A.x , B.y-A.y , D.x-C.x , D.y-C.y);
 87 }
 88 
 89 /*计算距离*/
 90 double distant(pos A,pos B)
 91 {
 92     return sqrt((B.x-A.x)*(B.x-A.x)+(B.y-A.y)*(B.y-A.y));
 93 }
 94 
 95 /*计算角度*/
 96 double angle(pos A,pos B,pos P)
 97 {
 98     return acos(dotdet(A.x-P.x,A.y-P.y,B.x-P.x,B.y-P.y)/(distant(A,P)*distant(B,P)));
 99 }
100 
101 /*凸包判断*/
102 bool IsConvexBag(pos* Vectex)
103 {
104     int direction=0;
105     //保存点集Vectex的旋转方向direction   1:右手正螺旋，逆时针   -1:左手正螺旋，顺时针
106     for(int i=0;i<=n-1;i++)
107     {
108         int temp=precision(cross(Vectex[i],Vectex[i+1],Vectex[i+1],Vectex[i+2]));
109 
110         if(!direction)   //避免最初的点出现共线的情况
111             direction=temp;
112 
113         if(direction*temp<0)  //只要Vectex是凸包，那么无论Vectex的旋转方向如何，direction*temp都会>=0
114             return false;
115     }
116     return true;
117 }
118 
119 /*判断点与多边形的关系*/
120 bool IsIn(pos* Vectex)
121 {
122     double CircleAngle=0.0;  //环绕角
123     for(int i=1;i<=n;i++)  //注意重复边不计算
124         if(precision(cross(Peg,Vectex[i],Peg,Vectex[i+1]))>=0)
125             CircleAngle+=angle(Vectex[i],Vectex[i+1],Peg);
126         else
127             CircleAngle-=angle(Vectex[i],Vectex[i+1],Peg);
128 
129     if(precision(CircleAngle)==0)  //CircleAngle=0, Peg在多边形外部
130         return false;
131     else if(precision(CircleAngle-pi)==0 || precision(CircleAngle+pi)==0)   //CircleAngle=180, Peg在多边形边上(不包括顶点)
132     {
133         if(precision(PegR)==0)
134             return true;
135     }
136     else if(precision(CircleAngle-2*pi)==0 || precision(CircleAngle+2*pi)==0)   //CircleAngle=360, Peg在多边形边内部
137         return true;
138     else   //CircleAngle=(0,360)之间的任意角， Peg在多边形顶点上
139     {
140         if(precision(PegR)==0)
141             return true;
142     }
143     return false;
144 }
145 
146 /*判断圆与多边形的关系*/
147 bool IsFit(pos* Vectex)
148 {
149     for(int i=0;i<=n;i++)
150     {
151         int k=precision(fabs(cross(Peg,Vectex[i],Peg,Vectex[i+1])/distant(Vectex[i],Vectex[i+1]))-PegR);
152         if(k<0)
153             return false;
154     }
155     
156     return true;
157 }

Sample Input

5 1.5 1.5 2.0
1.0 1.0
2.0 2.0
1.75 2.0
1.0 3.0
0.0 2.0
5 1.5 1.5 2.0
1.0 1.0
2.0 2.0
1.75 2.5
1.0 3.0
0.0 2.0
3  0.1  0.2 0.0
-0.5 1.0
0.5 -1.0
0.5 1.0
3  0.25  0.2 0.0
-0.5 1.0
0.5 -1.0
0.5 1.0
3 0.1 1.6 1.2
1.0 1.0
2.0 1.0
1.0 2.0
6 0.1 1.6 1.2
1.0 1.0
1.5 1.0
2.0 1.0
1.2 1.8
1.0 2.0
1.0 1.5
3 0.1 2.0 2.0
1.0 1.0
2.0 1.0
1.0 2.0
4  1.0  2.0 1.0
0.0 0.0
0.0 4.0
4.0 4.0
4.0 0.0
4  1.0  3.5 1.0
0.0 0.0
0.0 4.0
4.0 4.0
4.0 0.0
4  0.2  1.5 1.0
1.0 1.0
2.0 2.0
1.0 3.0
0.0 2.0
4  0.4  1.5 1.0
1.0 1.0
2.0 2.0
1.0 3.0
0.0 2.0
5  0.2  1.5 2.5
1.0 1.0
2.0 2.0
1.75 2.75
1.0 3.0
0.0 2.0
5  0.2  1.5 2.5
1.0 1.0
2.0 2.0
1.75 2.5
1.0 3.0
0.0 2.0
9 0.2 0.5 2.5
0.0 0.0
1.0 0.0
1.0 1.0
2.0 1.0
2.0 0.0
3.0 0.0
3.0 5.0
1.5 5.0
0.0 5.0
9 0.2 0.5 2.5
0.0 0.0
1.0 0.0
1.0 -1.0
2.0 -1.0
2.0 0.0
3.0 0.0
3.0 5.0
1.5 5.0
0.0 5.0
7 0.2 0.5 2.5
0.0 0.0
1.0 0.0
2.0 0.0
3.0 0.0
3.0 5.0
1.5 5.0
0.0 5.0
4 0.1 1 0.5
0 2
1 0
2 2
1 1
1

Sample Output

HOLE IS ILL-FORMED
PEG WILL NOT FIT
PEG WILL FIT
PEG WILL NOT FIT
PEG WILL FIT
PEG WILL FIT
PEG WILL NOT FIT
PEG WILL FIT
PEG WILL NOT FIT
PEG WILL NOT FIT
PEG WILL NOT FIT
PEG WILL FIT
PEG WILL NOT FIT
HOLE IS ILL-FORMED
HOLE IS ILL-FORMED
PEG WILL FIT
HOLE IS ILL-FORMED