poj A Round Peg in a Ground Hole

http://poj.org/problem?id=1584

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=;
const double pi=acos(-1.0);
const double eps=10e-; int cmp(double x)
{
if(fabs(x)<eps) return ;
if(x>) return ;
return -;
} double sqr(double x)
{
return x*x;
} struct point
{
double x,y;
point(){}
point(double a,double b):x(a),y(b){}
bool operator <(const point &a)const
{
return (x<a.x)||(x==a.x&&y<a.y);
}
friend point operator -(const point &a,const point &b){
return point(a.x-b.x,a.y-b.y);
}
double norm(){
return sqrt(sqr(x)+sqr(y));
}
}p[maxn],ch[maxn]; struct line
{
point a,b;
line(){}
line(point x,point y):a(x),b(y){}
}; double det(point a,point b,point c)
{
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
} double cross(point a,point b,point c)
{
return ((b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y));
}
double det1(const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
} double dot(const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
} double dis(point a,point b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
} double dis_point_segment(const point p,const point s,const point t)
{
if(cmp(dot(p-s,t-s))<) return (p-s).norm();
if(cmp(dot(p-t,s-t))<) return (p-t).norm();
return fabs(det1(s-p,t-p)/dis(s,t));
} bool pointonsegment(point p,point s,point t)
{
return cmp(det1(p-s,t-s))==&&cmp(dot(p-s,p-t))<=;
} int convex_hull(point *p,int n,point *ch)
{
sort(p,p+n);
int m=;
for(int i=; i<n; i++)
{
while(m>&&det(ch[m-],ch[m-],p[i])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-; i>=; i--)
{
while(m>k&&det(ch[m-],ch[m-],p[i])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;
} bool convex_hull1(point *p,int n)
{
int flag=;
p[n]=p[];
for(int i=; i<=n; i++)
{
//printf("%lf%lf %lf%lf %lf%lf\n",p[i-2].x,p[i-2].y,p[i-1].x,p[i-1].y,p[i].x,p[i].y);
int t=cmp(cross(p[i-],p[i-],p[i]));
//printf("%d\n",t);
if(!flag) flag=t;
if(flag*t<) return false;
}
return true;
}
int point_in(point t,point *ch,int n)
{
int num=,d1,d2,k;
ch[n]=ch[];
for(int i=; i<n; i++)
{
if(pointonsegment(t,ch[i],ch[i+])) return ;
k=cmp(det1(ch[i+]-ch[i],t-ch[i]));
d1=cmp(ch[i].y-t.y);
d2=cmp(ch[i+].y-t.y);
if(k>&&d1<=&&d2>) num++;
if(k<&&d2<=&&d1>) num--;
}
return num!=;
}
int main()
{
int n;
double r,x,y;
//freopen("sb.txt","w",stdout);
while(scanf("%d",&n)!=EOF)
{
if(n<) break;
scanf("%lf%lf%lf",&r,&x,&y);
point t(x,y);
for(int i=; i<n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
} if(!convex_hull1(p,n))
{
printf("HOLE IS ILL-FORMED\n");
continue;
}
int cn=convex_hull(p,n,ch);
if(point_in(t,ch,cn))
{
double max1=dis_point_segment(t,ch[],ch[]);
for(int i=; i<cn+; i++)
{
max1=min(max1,dis_point_segment(t,ch[i-],ch[i]));
}
if(max1-r>=) printf("PEG WILL FIT\n");
else printf("PEG WILL NOT FIT\n");
}
else printf("PEG WILL NOT FIT\n");
}
return ;
}
上一篇:delphi的webBrowser操作HTML研究


下一篇:sgu Ice-cream Tycoon