uva 1298 - Triathlon-程序员宅基地

半平面交的题；

这个题目的亮点就是建模；

#include<cstdio>
#include<algorithm>
#include<cmath>
#define maxn 109
#define eps 1e-6
using namespace std;

int dcmp(double x)
{
    return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1);
}

struct Point
{
    double x;
    double y;
    Point(double x = 0, double y = 0):x(x), y(y) {}
};
typedef Point Vector;

Vector operator + (Point A, Point B)
{
    return Vector(A.x + B.x, A.y + B.y);
}

Vector operator - (Point A, Point B)
{
    return Vector(A.x - B.x, A.y - B.y);
}

Vector operator * (Point A, double p)
{
    return Vector(A.x * p, A.y * p);
}

Vector operator / (Point A, double p)
{
    return Vector(A.x / p, A.y / p);
}
double dot(Point a,Point b)
{
    return a.x*b.x+a.y*b.y;
}
double cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}

Vector nomal(Vector a)
{
    double l=sqrt(dot(a,a));
    return Vector(-a.y/l,a.x/l);
}

struct line
{
    Point p;
    Vector v;
    double ang;
    line() {}
    line(Point p,Vector v):p(p),v(v)
    {
        ang=atan2(v.y,v.x);
    }
    bool operator<(const line &t)const
    {
        return ang<t.ang;
    }
};

bool onleft(line l,Point p)
{
    return (cross(l.v,p-l.p)>0);
}

Point getintersection(line a,line b)
{
    Vector u=a.p-b.p;
    double t=cross(b.v,u)/cross(a.v,b.v);
    return a.p+a.v*t;
}

int halfplanintersection(line *l,int n,Point *poly)
{
    sort(l,l+n);
    int first,last;
    Point *p=new Point[n];
    line *q=new line[n];
    q[first=last=0]=l[0];
    for(int i=1; i<n; i++)
    {
        while(first<last && !onleft(l[i],p[last-1]))last--;
        while(first<last && !onleft(l[i],p[first]))first++;
        q[++last]=l[i];
        if(fabs(cross(q[last].v,q[last-1].v))<eps)
        {
            last--;
            if(onleft(q[last],l[i].p))q[last]=l[i];
        }
        if(first<last)p[last-1]=getintersection(q[last-1],q[last]);
    }
    while(first<last && !onleft(q[first],p[last-1]))last--;
    if((last-first )<=1)return 0;
    p[last]=getintersection(q[last],q[first]);
    int m=0;
    for(int i=first; i<=last; i++)poly[m++]=p[i];
    return m;
}

Point poly[maxn];
line l[maxn];
double v[maxn],u[maxn],w[maxn];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)scanf("%lf%lf%lf",&v[i],&u[i],&w[i]);
        for(int i=0;i<n;i++)
        {
            double k=10000;
            bool flag=1;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i==j)continue;
                if(v[j]>=v[i]&&u[j]>=u[i]&&w[j]>=w[i]){flag=0;break;}
                if(v[j]<=v[i]&&w[j]<=u[i]&&w[j]<=w[i])continue;
                double a=(k/v[j]-k/w[j])-(k/v[i]-k/w[i]);
                double b=(k/u[j]-k/w[j])-(k/u[i]-k/w[i]);
                double c=k/w[j]-k/w[i];
                Point p;
                Vector v(b,-a);
                if(fabs(a)>fabs(b))p=Point(-c/a,0);
                else p=Point(0,-c/b);
                l[cnt++]=line(p,v);
            }
            if(flag)
            {
                l[cnt++]=line(Point(0,0),Vector(0,-1));
                l[cnt++]=line(Point(0,0),Vector(1,0));
                l[cnt++]=line(Point(0,1),Vector(-1,1));
                if(halfplanintersection(l,cnt,poly)==0)flag=0;
            }
            if(flag)puts("Yes");
            else puts("No");
        }

    }return 0;
}