【poj3130】How I Mathematician Wonder What You Are!

2015.03.13 15:24 Fri | 1次阅读 | 旧日oi | 固定链接 | 源码

题意

半平面交模板

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 110
#define eps 1e-9
#define DCMP(a) (fabs(a)<eps?1:0)
using namespace std;
struct Point{
    double x,y;
    Point (double _=0.0,double __=0.0):x(_),y(__) {}
    Point operator +(const Point &a)const{
        return Point(x+a.x,y+a.y);
    }
    Point operator -(const Point &a) const{
        return Point(x-a.x,y-a.y);
    }
    Point operator * (double a) const{
        return Point(x*a,y*a);
    }
    void operator +=(const Point &a){
        x+=a.x;y+=a.y;
    }
    void read(){
        scanf("%lf%lf",&x,&y);
    }
}point[maxn],p[maxn];
struct Line{
    Point p,v;
    double alpha;
    bool operator < (const Line &a) const{
        return alpha<a.alpha;
    }
    Line (Point _,Point __): p(_),v(__){
        alpha=atan2(v.y,v.x);
    }
    Line(){}
}line[maxn],q[maxn];
int n,cnt;
double cross(const Point &a,const Point &b);
bool onleft(const Line &l,const Point &p);
bool halfplaneintersection();
Point get_intersection(const Line &a,const Line &b);
int main()
{
    while(cin>>n&&n)
    {
        cnt=0;
        for(int i=1;i<=n;i++) point[i].read();
        for(int i=1;i<n;i++) line[++cnt]=Line(point[i],point[i+1]-point[i]);
        line[++cnt]=Line(point[n],point[1]-point[n]);
        sort(line+1,line+cnt+1);
        bool ans=halfplaneintersection();
        if(ans) puts("1");
        else puts("0");
    }
    return 0;
}
double cross(const Point &a,const Point &b)
{
    return a.x*b.y-a.y*b.x;
}
bool onleft(const Line &l,const Point &p)
{
    return cross(l.v,p-l.p)>=0;
}
bool halfplaneintersection()
{
    int front=1,tail=1;
    q[1]=line[1];
    for(int i=2;i<=cnt;i++)
    {
        while(front<tail&&!onleft(line[i],p[tail-1])) tail--;
        while(front<tail&&!onleft(line[i],p[front])) front++;
        if(DCMP(cross(line[i].v,q[tail].v))) 
        q[tail]=onleft(q[tail],line[i].p)?line[i]:q[tail];
        else q[++tail]=line[i];
        if(front<tail) p[tail-1]=get_intersection(q[tail],q[tail-1]);
    }
    while(front<tail&&!onleft(q[front],p[tail-1])) tail--;
    if(tail-front<=1) return 0;
    return tail>front;
}
Point get_intersection(const Line &a,const Line &b)
{
    Point u=a.p-b.p;
    double tmp=cross(b.v,u)/cross(a.v,b.v);
    return a.p+a.v*tmp;
}```