URAL 1062 - Triathlon（半平面交）

這個題乍眼一看好像很簡單，然後我就認為u、v、w只要有全部比另外一個人小的就不能win，否則就能win，但是這個思路只對了一半

不能win的結論是正確的，但是win的結論不止排除這一個條件

將這個人與其他人的條件列式

如果都win的話，則滿足 x/v+y/u+(k-x-y)/w（i的）<x/v+y/u+(k-x-y)/w（j的）由此構成n條直線（半平面），然後求交，如果有交集，則輸出Yes，否則No

#include <stdio.h>   
#include <math.h>   
#include <algorithm>   
using namespace std;  
const double eps = 1e-8;  
  
struct Point  
{  
    double x,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);  
}  
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& L) const  
    {  
        return ang<L.ang;  
    }  
};  
  
double Cross(Vector A, Vector B)  
{  
    return A.x*B.y - A.y*B.x;  
}  
  
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 Point(a.p.x+a.v.x*t, a.p.y+a.v.y*t);  
}  
  
int BPMJ(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;  
}  
  
double k=10000.0;  
int u[110],v[110],w[110];  
Point poly[110];  
Line L[110];  
  
int main()  
{  
    int n;  
    while(scanf("%d",&n)==1)  
    {  
        for(int i=0; i<n; i++)  
        {  
            scanf("%d%d%d",&u[i],&v[i],&w[i]);  
        }  
        for(int i=0; i<n; i++)  
        {  
            int f=0;  
            for(int j=0; j<n; j++)  
            {  
                if(j!=i && u[i]<=u[j] && v[i]<=v[j] && w[i]<=w[j])  
                {  
                    f=1;  
                    break;  
                }  
            }  
            if(f==1)  
                printf("No\n");  
            else  
            {  
                Point p;  
                int ct=0;  
                for(int j=0; j<n; j++)  
                {  
                    if(j!=i && u[i]>=u[j] && v[i]>=v[j] && w[i]>=w[j])  
                        continue;  
                    else if(j!=i)  
                    {  
                        double A=k/v[j]-k/v[i]-k/w[j]+k/w[i];  
                        double B=k/u[j]-k/u[i]-k/w[j]+k/w[i];  
                        double C=k/w[j]-k/w[i];  
                        if(fabs(A)>fabs(B))  
                            p=Point(-C/A,0);  
                        else  
                            p=Point(0,-C/B);  
                        Vector v(B,-A);  
                        L[ct++] = Line(p,v);  
                    }  
                }  
                L[ct++] = Line(Point(0,0), Vector(0,-1));  
                L[ct++] = Line(Point(0,0), Vector(1,0));  
                L[ct++] = Line(Point(0,1), Vector(-1,1));  
                if(BPMJ(L,ct,poly))printf("Yes\n");  
                else printf("No\n");  
            }  
        }  
    }  
    return 0;  
}  

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double eps = 1e-8;

struct Point
{
    double x,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);
}
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& L) const
    {
        return ang<L.ang;
    }
};

double Cross(Vector A, Vector B)
{
    return A.x*B.y - A.y*B.x;
}

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 Point(a.p.x+a.v.x*t, a.p.y+a.v.y*t);
}

int BPMJ(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;
}

double k=10000.0;
int u[110],v[110],w[110];
Point poly[110];
Line L[110];

int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        for(int i=0; i<n; i++)
        {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
        }
        for(int i=0; i<n; i++)
        {
            int f=0;
            for(int j=0; j<n; j++)
            {
                if(j!=i && u[i]<=u[j] && v[i]<=v[j] && w[i]<=w[j])
                {
                    f=1;
                    break;
                }
            }
            if(f==1)
                printf("No\n");
            else
            {
                Point p;
                int ct=0;
                for(int j=0; j<n; j++)
                {
                    if(j!=i && u[i]>=u[j] && v[i]>=v[j] && w[i]>=w[j])
                        continue;
                    else if(j!=i)
                    {
                        double A=k/v[j]-k/v[i]-k/w[j]+k/w[i];
                        double B=k/u[j]-k/u[i]-k/w[j]+k/w[i];
                        double C=k/w[j]-k/w[i];
                        if(fabs(A)>fabs(B))
                            p=Point(-C/A,0);
                        else
                            p=Point(0,-C/B);
                        Vector v(B,-A);
                        L[ct++] = Line(p,v);
                    }
                }
                L[ct++] = Line(Point(0,0), Vector(0,-1));
                L[ct++] = Line(Point(0,0), Vector(1,0));
                L[ct++] = Line(Point(0,1), Vector(-1,1));
                if(BPMJ(L,ct,poly))printf("Yes\n");
                else printf("No\n");
            }
        }
    }
    return 0;
}