poj 1584 A Round Peg in a Ground Hole(计算几何)

题目：http://poj.org/problem?id=1584

参考的别人的解题报告。。。。

题意：

按照顺时针或逆时针方向输入一个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，则说明圆在多边形内

代码：

View Code

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #define PI 3.141592654
  5 
  6 using namespace std;
  7 const double eps=1e-6;
  8 typedef struct node
  9 {
 10     double x,y;
 11 }point;
 12 point ver[155];
 13 double r;
 14 point pt;
 15 int n;
 16 //三态函数
 17 int dcml(double x)
 18 {
 19     if(fabs(x)<eps)
 20     return 0;
 21     else if(x>0)
 22     return 1;
 23     else
 24     return -1;
 25 }
 26 //叉积
 27 double det(double x1,double y1,double x2,double y2)
 28 {
 29     return x1*y2-x2*y1;
 30 }
 31 double cross(point a,point b,point c,point d)
 32 {
 33     return det(b.x-a.x,b.y-a.y,d.x-c.x,d.y-c.y);
 34 }
 35 
 36 
 37 //判断是否为凸包
 38 int pantubao()
 39 {
 40     int i;
 41 
 42         double dis=dcml(cross(ver[0],ver[1],ver[1],ver[2]));
 43         double h;
 44         for(i=1;i<n;i++)
 45         {
 46             h=dcml(cross(ver[i],ver[i+1],ver[i+1],ver[i+2]));
 47             if(h*dis<0)
 48             return 0;
 49         }
 50         return 1;
 51 }
 52 //点乘
 53 double dot(double x1,double y1,double x2,double y2)
 54 {
 55     return x1*x2+y1*y2;
 56 }
 57 double xiangliang(point p,point b,point c)
 58 {
 59     return dot(b.x-p.x,b.y-p.y,c.x-p.x,c.y-p.y);
 60 }
 61 //距离
 62 double dist(point a,point b)
 63 {
 64     return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
 65 }
 66 //角度
 67 double angel(point p,point b,point c)
 68 {
 69     return acos(xiangliang(p,b,c)/(dist(b,p)*dist(c,p)));
 70 }
 71 //判断圆心位置
 72 int panyuan()
 73 {
 74     double sumangel=0;
 75     int i;
 76     for(i=1;i<=n;i++)
 77     {
 78         if(dcml(cross(pt,ver[i],pt,ver[i+1]))>=0)
 79         sumangel+=angel(pt,ver[i],ver[i+1]);
 80         else
 81         sumangel-=angel(pt,ver[i],ver[i+1]);
 82     }
 83     //cout<<sumangel<<endl;
 84     if(dcml(sumangel)==0)//圆心在多边形外部
 85     {
 86         return 0;
 87     }
 88     else if(dcml(sumangel-PI)==0||dcml(sumangel+PI)==0)//圆心在多边形边上
 89     {
 90         if(dcml(r)==0)
 91         return 1;
 92         return 0;
 93     }
 94     else if(dcml(sumangel-(2*PI))==0||dcml(sumangel+(2*PI))==0)//圆心在多边形内部
 95     {
 96         return 1;
 97     }
 98     else//圆心在多边形顶点上
 99     {
100         if(dcml(r)==0)
101         return 1;
102         //cout<<"()"<<endl;
103         return 0;
104     }
105     return 0;
106 }
107 
108 int panr()
109 {
110     int i;
111     for(i=0;i<=n;i++)
112     {
113         int s=dcml(fabs(cross(pt,ver[i],pt,ver[i+1])/dist(ver[i],ver[i+1]))-r);
114         if(s<0)
115         return 0;
116     }
117     return 1;
118 }
119 int main()
120 {
121 
122     while(scanf("%d",&n)!=EOF)
123     {
124         if(n<3)
125         break;
126         scanf("%lf%lf%lf",&r,&pt.x,&pt.y);
127         int i;
128         for(i=1;i<=n;i++)
129         {
130             scanf("%lf%lf",&ver[i].x,&ver[i].y);
131         }
132         ver[0].x=ver[n].x;
133         ver[0].y=ver[n].y;
134         ver[n+1].x=ver[1].x;
135         ver[n+1].y=ver[1].y;
136         int flag;
137         flag=pantubao();
138         if(!flag)
139         {
140             printf("HOLE IS ILL-FORMED\n");
141             continue;
142         }
143         int flag1=panyuan();
144         int flag2=panr();
145         //cout<<"flag1="<<flag1<<" "<<"flag2="<<flag2<<endl;
146         if(flag1==1&&flag2==1)
147         printf("PEG WILL FIT\n");
148         else
149         printf("PEG WILL NOT FIT\n");
150     }
151     return 0;
152 }