POJ 1584 A Round Peg in a Ground Hole[判断凸包 点在多边形内]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N=1005;
const double eps=1e-8;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
    return x*f;
}
inline int sgn(double x){
    if(abs(x)<eps) return 0;
    else return x<0?-1:1;
}
struct Vector{
    double x,y;
    Vector(double a=0,double b=0):x(a),y(b){}
    bool operator <(const Vector &a)const{
        return x<a.x||(x==a.x&&y<a.y);
    }
    void print(){
        printf("%lf %lf\n",x,y);
    }
};
typedef Vector Point;
Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}

double Cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}
double Dot(Vector a,Vector b){
    return a.x*b.x+a.y*b.y;
}

double Len(Vector a){return sqrt(Dot(a,a));}
double DisTS(Point p,Point a,Point b){
    if(a==b) return Len(p-a);
    Vector v1=b-a,v2=p-a,v3=p-b;
    if(sgn(Dot(v1,v2))<0) return Len(v2);
    else if(sgn(Dot(v1,v3))>0) return Len(v3);
    else return abs(Cross(v1,v2)/Len(v1));
}
int PointInPolygon(Point p,Point poly[],int n){
    int wn=0;
    for(int i=0;i<n;i++){
        if(sgn(DisTS(p,poly[i],poly[(i+1)%n]))==0) return -1;
        int k=sgn(Cross(poly[(i+1)%n]-poly[i],p-poly[i])),
        d1=sgn(poly[i].y-p.y),d2=sgn(poly[(i+1)%n].y-p.y);
        if(k>0&&d1<=0&&d2>0) wn++;
        if(k<0&&d2<=0&&d1>0) wn--;
    }
    return (bool)wn;
}
bool isConvex(Point poly[],int n){
    int last=0,now=0;
    for(int i=0;i<n;i++){
        now=sgn(Cross(poly[(i+1)%n]-poly[i],poly[(i+2)%n]-poly[(i+1)%n]));
        if(last==0||now==0||now*last>0) last=now;
        else return false;
    }
    return true;
}
int n;
double r,x,y,x2,y2;
Point poly[N];
void solve(){
    if(isConvex(poly,n)){
        Point c(x,y);
        if(PointInPolygon(c,poly,n)){
            int flag=1;
            for(int i=0;i<n;i++)
                if(sgn(DisTS(c,poly[i],poly[(i+1)%n])-r)<0){flag=0;break;}
            if(flag) puts("PEG WILL FIT");
            else puts("PEG WILL NOT FIT");
        }else puts("PEG WILL NOT FIT");
    }else puts("HOLE IS ILL-FORMED");
}
int main(int argc, const char * argv[]) {
    while(true){
        n=read();if(n<3) break;
        scanf("%lf%lf%lf",&r,&x,&y);
        for(int i=0;i<n;i++)
            scanf("%lf%lf",&poly[i].x,&poly[i].y);
        solve();
    }
    return 0;
}