266
POJ 1584 判斷凸包，點在多邊形內外，點到直線最短距離
題意求給出一個多邊形，問這個多邊形是否是凸包，如果不是數出HOLE IS ILL-FORMED，如果是問一個棍子能否穿過，給出底麵的圓心和半徑。
分3步：
1、判斷是否是凸多邊形
2、判斷點是否在多邊形內部
3、判斷點到各邊的最小距離是否大於等於半徑
由於輸入是按照順時針或者逆時針，所以隻要判斷相鄰叉積同號就可以。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
PointType x,y;
};
point data[160];
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi. x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int Graham_Scan(point *a,int numa)
{
for(int i=0; i<numa; i++)
if(Direction(a[i],a[(i+1)%numa],a[(i+2)%numa])*Direction(a[(i+1)%numa],a[(i+2)%numa],a[(i+3)%numa])<0)
return 0;
return 1;
}
bool On_Segment(point pi,point pj,point pk)
{
if(pk.x>=min(pi.x,pj.x)&&pk.x<=max(pi.x,pj.x)&&pk.y>=min(pi.y,pj.y)&&pk.y<=max(pi.y,pj.y))
return 1;
return 0;
}
bool Segment_Intersect(point p1,point p2,point p3,point p4)
{
PointType d1=Direction(p3,p4,p1),d2=Direction(p3,p4,p2),d3=Direction(p1,p2,p3),d4=Direction(p1,p2,p4);
if(((d1>0&&d2<0)||(d1<0&&d2>0))&&((d3>0&&d4<0)||(d3<0&&d4>0)))
return 1;
if(d1==0&&On_Segment(p3,p4,p1))
return 1;
if(d2==0&&On_Segment(p3,p4,p2))
return 1;
if(d3==0&&On_Segment(p1,p2,p3))
return 1;
if(d4==0&&On_Segment(p1,p2,p4))
return 1;
return 0;
}
int Pandingdian(point a,int n,point *polygon)//1在多邊形上 2在多邊形外 0在多邊形內
{
point b;
b.x=-9999999;
b.y=a.y;
int sum=0;
polygon[n]=polygon[0];
for(int i=1; i<=n; i++)
if(polygon[i].y-polygon[i-1].y!=0&&Segment_Intersect(a,b,polygon[i],polygon[i-1]))
{
if(Direction(a,polygon[i],polygon[i-1])==0)
return 1;
sum++;
}
if(sum&1)
return 0;
return 2;
}
double DotProduct(point p0,point p1,point p2)
{
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
double MinDistance(point p0,point p1,point p2)
{
double d=Dis(p1,p2);
double u=DotProduct(p1,p0,p2)/(d*d);
if(u<0)
return Dis(p0,p1);
else if(u>1)
return Dis(p0,p2);
else
{
point v;
v.x=p1.x+u*(p2.x-p1.x);
v.y=p1.y+u*(p2.y-p1.y);
return Dis(p0,v);
}
}
int main()
{
point center;
double bj;
int n;
while(~scanf("%d",&n),n>2)
{
scanf("%lf%lf%lf",&bj,¢er.x,¢er.y);
for(int i=0; i<n; i++)
scanf("%lf%lf",&data[i].x,&data[i].y);
if(!Graham_Scan(data,n))
{
puts("HOLE IS ILL-FORMED");
continue;
}
if(Pandingdian(center,n,data))
{
puts("PEG WILL NOT FIT");
continue;
}
int f=1;
for(int i=0; i<n; i++)
if(MinDistance(center,data[i],data[(i+1)%n])<bj)
{
f=0;
break;
}
if(f)
puts("PEG WILL FIT");
else
puts("PEG WILL NOT FIT");
}
return 0;
}
最後更新：2017-04-03 22:15:39