BZOJ3800 Saber VS Lancer

2014.12.16 13:53 Tue| 11 visits oi_2015| 2015_刷题日常| Text

BZOJ你为什么这么坑 T_T

WA了一回,然后刚准备交第二次,却发现几分钟不见,这一道题却已变土豪

恍若隔世应该便说的是这样一个道理罢……

Solution

参见刘汝佳白书280页。

Code

#include <bits/stdc++.h>
using namespace std;
#define sqr(x) ((x)*(x))
#define dcmp(x) (fabs(x)<1e-10)
#define N 105
#define S 10000

struct point
{
    double x,y;
    point(double _x=0.0,double _y=0.0):x(_x),y(_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 *(const double a) const
    {
        return point(x*a,y*a);
    }
    friend double cross(const point &a,const point &b)
    {
        return a.x*b.y-a.y*b.x;
    }
    friend double dist(const point &a,const point &b)
    {
        return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
    }
    inline void read()
    {
        cin>>x>>y;
    }
};

struct line
{
    point p,v; double t;
    line() {}
    line(point _p,point _v):p(_p),v(_v)
    {
        t=atan2(v.y,v.x);
    }
    bool operator <(const line &a) const
    {
        return t<a.t;
    }
    friend bool left(const point &p,const line &l)
    {
        return cross(l.v,p-l.p)>=0;
    }
    friend point intersection(const line &a,const line &b)
    {
        return a.p+a.v*(cross(b.v,a.p-b.p)/cross(a.v,b.v));
    }
};

int n,head,tail;
double v[N],u[N],w[N];
point vertex[N]; line deq[N],l[N];

bool half_plane_intersection(int tot)
{
    sort(l+1,l+tot+1);
    head=tail=0; deq[tail++]=l[1];
    for(int i=2;i<=tot;i++)
    {
        while(tail-head>=2&&!left(vertex[tail-1],l[i])) tail--;
        while(tail-head>=2&&!left(vertex[head+1],l[i])) head++;
        if(dcmp(l[i].t-deq[tail-1].t))
            deq[tail-1]=left(l[i].p,deq[tail-1])?l[i]:deq[tail-1];
        else deq[tail++]=l[i];
        if(tail-head>=2) vertex[tail-1]=intersection(deq[tail-2],deq[tail-1]);
    }
    while(tail-head>=2&&!left(vertex[tail-1],deq[head])) tail--;
    vertex[head]=intersection(deq[tail-1],deq[head]);
    return tail-head>2;
}

double get_area()
{
    double re=0;
    for(int i=head+1;i<=tail-2;i++)
        re+=cross(vertex[i]-vertex[head],vertex[i+1]-vertex[head]);
    return re/2;
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>u[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        bool flag=true; int tot=0;
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(v[i]<=v[j]&&u[i]<=u[j]&&w[i]<=w[j]){ flag=0; break; }
            if(v[i]>=v[j]&&u[i]>=u[j]&&w[i]>=w[j]) continue;
            double a=(S/v[j]-S/w[j])-(S/v[i]-S/w[i]), b=(S/u[j]-S/w[j])-(S/u[i]-S/w[i]), c=S/w[j]-S/w[i];
            l[++tot]=line(fabs(a)>fabs(b)?point(-c/a,0):point(0,-c/b),point(b,-a));
        }
        if(flag)
        {
            l[++tot]=line(point(0,0),point(0,-1));
            l[++tot]=line(point(0,0),point(1,0));
            l[++tot]=line(point(0,1),point(-1,1));
            if(!half_plane_intersection(tot)) flag=false;
        }
        puts(flag?"Yes":"No");
    }
}