POJ1755 - Triathlon

题意

已知每位运动员在铁人三项三段路上的速度，问：如果可以任意指定路段的长度，哪些运动员可以拿到第一（唯一的）。

思路

不难想到，如果一共有$n$个运动员，编号分别为$1,2,…,n$，那么若第$i$​个运动员能够获胜，则需满足：

$\frac{x}{v_{1i}} + \frac{y}{v_{2i}} + \frac{z}{v_{3i}} < \frac{x}{v_{1j}} + \frac{y}{v_{2j}} + \frac{z}{v_{3j}}, \quad i \neq j, 1 \leq i \leq n, 1 \leq j \leq n$​​

如果详细列举出来，则一共有$n-1$条不等式需要满足，这些不等式中有三个变量$x,y,z$

但实际上，变量只有两个。我们假设总路长为$L$，那么可以假设$x,y,z$为每段路的占比，那么$z = (1 - x - y)$。如果这样写，问题就可以转化为半平面交。

特别要注意的是：

如果将$x,y,z$​转化为占比，则边界为$x + y < 1, 0 < x < 1, 0 < y < 1$​。

如果不转化为占比，我们也可以考虑除以某一变量，如构造：

$x’ = x / z, y’ = y / z, z’ = z / z = 1$​​

此时$x’,y’$​​成为新的变量。由于我们只需要判断$Yes/No$​，不需要求解具体的情况，因此也不需要把变量还原回去，只要使用这个新的变量$x’,y’$​​来半平面交就可以了。

那么，不等式组转化为：

$\frac{x'}{v_{1i}} + \frac{y'}{v_{2i}} + \frac{1}{v_{3i}} < \frac{x'}{v_{1j}} + \frac{y'}{v_{2j}} + \frac{1}{v_{3j}}, \quad i \neq j, 1 \leq i \leq n, 1 \leq j \leq n$​​

对这$n-1$个不等式做半平面交即可。

代码

需要注意几个特殊情况

• 垂直和平行的向量需要特殊处理一下方向，因为一般半平面交的代码默认将向量左边（逆时针）作为求解方向，如果不统一方向求解起来会比较困难。
• 如果有$v1,v2$都相等，但$v3$获胜的情况也需要特判一下，否则构造直线时会除$0$导致$re$​。

// 1755.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 1505
using namespace std;
const double eps = 1e-8;
int sgn(double x){
    if(fabs(x) < eps)    return 0;
    return x > 0 ? 1 : -1;
}
struct Point{
    double x, y;
    Point(){}
    Point(double _x, double _y){ x = _x; y = _y; }
    Point operator +(const Point &A){
        return Point(x + A.x, y + A.y);
    }
    Point operator -(const Point &A){
        return Point(x - A.x, y - A.y);
    }
    double operator *(const Point &A){
        return x * A.x + y * A.y;
    }
    double operator ^(const Point &A){
        return x * A.y - y * A.x;
    }
    bool operator == (const Point &A){
        return sgn(x - A.x) == 0 && sgn(y - A.y) == 0;
    }
    void print(){
        printf("[Point] %.6lf %.6lf\n", x, y);
    }
    void input(){
        cin >> x >> y;
    }
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point _s, Point _e){ s = _s; e = _e; }
    bool parallel(Line v){
        return sgn((e - s) ^ (v.e - v.s)) == 0;
    }
    Point crosspoint(Line v){
        double a1 = (v.e - v.s) ^ (s - v.s);
        double a2 = (v.e - v.s) ^ (e - v.s);
        return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
    }
    void print(){
        printf("[Line] %.6lf %.6lf %.6lf %.6lf\n", s.x, s.y, e.x, e.y);
    }
};
struct polygon{
    int n;
    Point p[maxn];
    Line l[maxn];
    void print(){
        printf("[Polygon] Number: %d\n", n);
        for(int i = 0; i < n; i++){
            p[i].print();
        }
    }
};
struct halfplane: public Line{
    double angle;
    halfplane(){}
    halfplane(Point _s, Point _e){ s = _s; e = _e; }
    halfplane(Line v) { s = v.s; e = v.e; };
    void calcangle(){
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator <(const halfplane &b){
        return angle < b.angle;
    }
};
struct halfplanes{
    int n;
    Point p[maxn];
    halfplane hp[maxn];
    int que[maxn], st, ed;
    void push(halfplane tmp){
        hp[n++] = tmp;
    }
    void unique(){
        int m = 1;
        for(int i = 1; i < n; i++){
            if(sgn(hp[i].angle - hp[i - 1].angle) != 0){
                hp[m++] = hp[i];
            }
            else if(sgn((hp[m - 1].e - hp[m - 1].s) ^ (hp[i].s - hp[m - 1].s)) > 0){
                hp[m - 1] = hp[i];
            }
        }
        n = m;
    }
    bool halfplaneinsert(){
        for(int i = 0; i < n; i++)    hp[i].calcangle();
        sort(hp, hp + n); unique();
        que[st = 0] = 0; que[ed = 1] = 1;
        p[1] = hp[0].crosspoint(hp[1]);
        for(int i = 2; i < n; i++){
            while(st < ed && sgn((hp[i].e - hp[i].s) ^ (p[ed] - hp[i].s)) < 0)    ed--;
            while(st < ed && sgn((hp[i].e - hp[i].s) ^ (p[st + 1] - hp[i].s)) < 0)    st++;
            que[++ed] = i;
            if(hp[i].parallel(hp[que[ed - 1]]))    return false;
            p[ed] = hp[i].crosspoint(hp[que[ed - 1]]);
        }
        while(st < ed && sgn((hp[que[st]].e - hp[que[st]].s) ^ (p[ed] - hp[que[st]].s)) < 0)    ed--;
        while(st < ed && sgn((hp[que[ed]].e - hp[que[ed]].s) ^ (p[st + 1] - hp[que[ed]].s)) < 0)    st++;
        if(st + 1 >= ed)    return false;
        return true;
    }
    void getconvex(polygon &con){
        p[st] = hp[que[st]].crosspoint(hp[que[ed]]);
        con.n = ed - st + 1;
        for(int i = 0, j = st; j <= ed; i++, j++){
            con.p[i] = p[j];
        }
    }
};
Line calc(double v1, double v2, double v3, double n1, double n2, double n3){
    static const Point INP = Point(0, 1e9), SP1 = Point(-1e9, 0), SP2 = Point(1e9, 0);
    double s1 = (v2 * n2) * (v3 * n3) * (n1 - v1);
    double s2 = (v1 * n1) * (v3 * n3) * (n2 - v2);
    double cv = (v1 * n1) * (v2 * n2) * (n3 - v3);
    Point res1, res2;
    if(sgn(s2)){
        res1 = Point(0, (-cv) / s2);
        res2 = Point(1, (-cv - s1) / s2);
    }
    else{
        res1 = Point((-cv) / s1, 0);
        res2 = Point((-cv - s2) / s1, 1);
    }
    if(sgn(res1.x - res2.x) == 0){
        if(s1 * SP1.x + s2 * SP1.y + cv < 0 && res1.y > res2.y)    swap(res1, res2);
        if(s1 * SP2.x + s2 * SP2.y + cv < 0 && res1.y < res2.y)    swap(res1, res2);
        return Line(res1, res2);
    }
    if(sgn(res1.y - res2.y) == 0){
        if(s1 * INP.x + s2 * INP.y + cv < 0 && res1.x > res2.x)    swap(res1, res2);
        if(s1 * INP.x + s2 * INP.y + cv > 0 && res1.x < res2.x)    swap(res1, res2);
        return Line(res1, res2);
    }
    if(sgn(s1 * INP.x + s2 * INP.y + cv) < 0){
        if(sgn(res1.x - res2.x) > 0)    swap(res1, res2);
        return Line(res1, res2);
    }
    else{
        if(sgn(res1.x - res2.x) < 0)    swap(res1, res2);
        return Line(res1, res2);
    }
}
int n;
struct speed{
    double v1, v2, v3;
}sp[maxn];
const double INF = 1e9;
int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> sp[i].v1 >> sp[i].v2 >> sp[i].v3;
    }
    for(int i = 1; i <= n; i++){
        int flag = 1, cntt = 0;
        for(int j = 1; j <= n; j++){
            if(i == j)    continue;
            if(sp[i].v1 <= sp[j].v1 && sp[i].v2 <= sp[j].v2 && sp[i].v3 <= sp[j].v3){
                printf("No\n");
                flag = 0;
                break;
            }
            if(sp[i].v1 == sp[j].v1 && sp[i].v2 == sp[j].v2 && sp[i].v3 > sp[j].v3){
                cntt++;
            }
        }
        if(!flag)    continue;
        if(cntt == n - 1){
            printf("Yes\n");
            continue;
        }
        halfplanes now; now.n = 0;
        for(int j = 1; j <= n; j++){
            if(i == j)    continue;
            now.push(halfplane(calc(sp[i].v1, sp[i].v2, sp[i].v3, sp[j].v1, sp[j].v2, sp[j].v3)));
        }   
        now.push(halfplane(Point(eps, eps), Point(INF, eps)));
        now.push(halfplane(Point(INF, eps), Point(INF, INF)));
        now.push(halfplane(Point(INF, INF), Point(eps, INF)));
        now.push(halfplane(Point(eps, INF), Point(eps, eps)));
        if(now.halfplaneinsert()){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    return 0;
}