poj A Round Peg in a Ground Hole

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cmath>
  4 #include<algorithm>
  5 using namespace std;
  6 
  7 const int maxn=50000;
  8 const double pi=acos(-1.0);
  9 const double eps=10e-8;
 10 
 11 int cmp(double x)
 12 {
 13    if(fabs(x)<eps) return 0;
 14    if(x>0) return 1;
 15    return -1;
 16 }
 17 
 18 double sqr(double x)
 19 {
 20     return x*x;
 21 }
 22 
 23 struct point
 24 {
 25     double x,y;
 26     point(){}
 27     point(double a,double b):x(a),y(b){}
 28     bool operator <(const point &a)const
 29     {
 30         return (x<a.x)||(x==a.x&&y<a.y);
 31     }
 32     friend point operator -(const point &a,const point &b){
 33         return point(a.x-b.x,a.y-b.y);
 34     }
 35     double norm(){
 36         return sqrt(sqr(x)+sqr(y));
 37     }
 38 }p[maxn],ch[maxn];
 39 
 40 struct line
 41 {
 42    point a,b;
 43    line(){}
 44    line(point x,point y):a(x),b(y){}
 45 };
 46 
 47 double det(point a,point b,point c)
 48 {
 49     return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
 50 }
 51 
 52 double cross(point a,point b,point c)
 53 {
 54     return ((b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y));
 55 }
 56 double det1(const point &a,const point &b)
 57 {
 58     return a.x*b.y-a.y*b.x;
 59 }
 60 
 61 double dot(const point &a,const point &b)
 62 {
 63     return a.x*b.x+a.y*b.y;
 64 }
 65 
 66 double dis(point a,point b)
 67 {
 68     return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
 69 }
 70 
 71 double dis_point_segment(const point p,const point s,const point t)
 72 {
 73     if(cmp(dot(p-s,t-s))<0) return (p-s).norm();
 74     if(cmp(dot(p-t,s-t))<0) return (p-t).norm();
 75     return fabs(det1(s-p,t-p)/dis(s,t));
 76 }
 77 
 78 bool pointonsegment(point p,point s,point t)
 79 {
 80     return cmp(det1(p-s,t-s))==0&&cmp(dot(p-s,p-t))<=0;
 81 }
 82 
 83 int convex_hull(point *p,int n,point *ch)
 84 {
 85     sort(p,p+n);
 86     int m=0;
 87     for(int i=0; i<n; i++)
 88     {
 89         while(m>1&&det(ch[m-2],ch[m-1],p[i])<=0) m--;
 90         ch[m++]=p[i];
 91     }
 92     int k=m;
 93     for(int i=n-2; i>=0; i--)
 94     {
 95         while(m>k&&det(ch[m-2],ch[m-1],p[i])<=0) m--;
 96         ch[m++]=p[i];
 97     }
 98     if(n>1) m--;
 99     return m;
100 }
101 
102 
103 bool convex_hull1(point *p,int n)
104 {
105     int flag=0;
106     p[n]=p[0];
107     for(int i=2; i<=n; i++)
108     {
109         //printf("%lf%lf %lf%lf %lf%lf
",p[i-2].x,p[i-2].y,p[i-1].x,p[i-1].y,p[i].x,p[i].y);
110         int t=cmp(cross(p[i-2],p[i-1],p[i]));
111         //printf("%d
",t);
112         if(!flag) flag=t;
113         if(flag*t<0) return false;
114     }
115     return true;
116 }
117 int point_in(point t,point *ch,int n)
118 {
119     int num=0,d1,d2,k;
120     ch[n]=ch[0];
121     for(int i=0; i<n; i++)
122     {
123         if(pointonsegment(t,ch[i],ch[i+1])) return 2;
124         k=cmp(det1(ch[i+1]-ch[i],t-ch[i]));
125         d1=cmp(ch[i].y-t.y);
126         d2=cmp(ch[i+1].y-t.y);
127         if(k>0&&d1<=0&&d2>0) num++;
128         if(k<0&&d2<=0&&d1>0) num--;
129     }
130     return num!=0;
131 }
132 int main()
133 {
134     int n;
135     double r,x,y;
136     //freopen("sb.txt","w",stdout);
137     while(scanf("%d",&n)!=EOF)
138     {
139         if(n<3) break;
140         scanf("%lf%lf%lf",&r,&x,&y);
141         point t(x,y);
142         for(int i=0; i<n; i++)
143         {
144             scanf("%lf%lf",&p[i].x,&p[i].y);
145         }
146 
147         if(!convex_hull1(p,n))
148         {
149             printf("HOLE IS ILL-FORMED
");
150             continue;
151         }
152         int cn=convex_hull(p,n,ch);
153         if(point_in(t,ch,cn))
154         {
155             double max1=dis_point_segment(t,ch[0],ch[1]);
156             for(int i=1; i<cn+1; i++)
157             {
158                 max1=min(max1,dis_point_segment(t,ch[i-1],ch[i]));
159             }
160             if(max1-r>=0) printf("PEG WILL FIT
");
161             else printf("PEG WILL NOT FIT
");
162         }
163         else printf("PEG WILL NOT FIT
");
164     }
165     return 0;
166 }
View Code