ZOJ - Triathlon(线性规划+半平面交)

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2052
Time Limit: 5 Seconds Memory Limit: 32768 KB

Description

Triathlon is an athletic contest consisting of three consecutive sections that should be completed as fast as possible as a whole. The first section is swimming, the second section is riding bicycle and the third one is running.

The speed of each contestant in all three sections is known. The judge can choose the length of each section arbitrarily provided that no section has zero length. As a result sometimes she could choose their lengths in such a way that some particular contestant would win the competition.

Input

The first line of the input contains integer number N (1 <= N <= 100), denoting the number of contestants. Then N lines follow, each line contains three integers Vi, Ui and Wi (1 <= Vi, Ui, Wi <= 10000), separated by spaces, denoting the speed of ith contestant in each section.

Output

For every contestant write to the output one line, that contains word "Yes" if the judge could choose the lengths of the sections in such a way that this particular contestant would win (i.e. she is the only one who would come first), or word "No" if this is impossible.

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

1

9
10 2 6
10 7 3
5 6 7
3 2 7
6 2 6
3 5 7
8 4 6
10 4 2
1 8 7

Sample Output

Yes
Yes
Yes
No
No
No
Yes
No
Yes

Problem solving report:

Description: 有n个人参加三项比赛，你作为一个裁判可以随意调整三个赛段的距离(都大于0)，问是否能调整使得指定的选手获胜。
Problem solving: 题目实际上是给出了n个式子方程，Ti=Ai*x+Bi*y+Ci*z，0<i<n。
要判断第i个人能否获胜，即判断不等式组Tj-Ti>0,0<j<n&&j!=i有解。
即(Aj-Ai)*x+(Bj-Bi)*y+(Cj-Ci)*z>0,0<j<n&&j!=i有解。
由于 z > 0, 所以可以两边同时除以z，将x/z，y/z分别看成未知数x和y，这样就化三维为二维，可用半平面交判断是否存在解了，对每个人构造一次，求一次半平面交即可。
我用的是ZZY的I&S算法的模版，做的过程中要将A*x+B*y+C>0表示的半平面，转化成由两点组成的向量表示。
首先，所有的半平面保证符号一致, 然后根据A，B，C的正负构造向量，取每个向量的左边为半平面。

Accepted Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const double eps = 1e-8;
const double inf = 1e10;
int u[MAXN], v[MAXN], w[MAXN];
typedef struct point {
    double x, y;
}vect;
struct line {
    vect p;
    point u, v;
    bool operator < (const line& s) const {
        return atan2(s.p.y, s.p.x) > atan2(p.y, p.x);
    }
}Sline[MAXN];
vect operator - (const point a, const point b) {
    return (vect){a.x - b.x, a.y - b.y};
}
int pnz(double x) {
    return x < -eps ? -1 : x > eps ? 1 : 0;
}
double Cross(const vect a, const vect b) {
    return a.x * b.y - a.y * b.x;
}
bool Onleft(const point p, const line l) {
    return pnz(Cross(l.p, p - l.u)) > 0;
}
point Inter(const line a, const line b) {
    double t = Cross(b.p, a.u - b.u) / Cross(a.p, b.p);
    return (point){a.u.x + t * a.p.x, a.u.y + t * a.p.y};
}
bool Halfplane(int n) {
    sort(Sline, Sline + n);
    point Spt[n];
    int Q[n] = {0};
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        while (l < r && !Onleft(Spt[r - 1], Sline[i]))
            r--;
        while (l < r && !Onleft(Spt[l], Sline[i]))
            l++;
        Q[++r] = i;
        if (!pnz(Cross(Sline[i].p, Sline[Q[r - 1]].p))) {
            r--;
            if (Onleft(Sline[i].u, Sline[Q[r]]))
                Q[r] = i;
        }
        else Spt[r - 1] = Inter(Sline[Q[r]], Sline[Q[r - 1]]);
    }
    while (l < r && !Onleft(Spt[r - 1], Sline[Q[l]]))
        r--;
    while (l < r && !Onleft(Spt[l], Sline[Q[r]]))
        l++;
    if (r - l <= 1)
        return false;
    return true;
}
int main() {
    int t, n;
    double a, b, c;
    point s, e, p[4];
    p[0] = (point){0, 0};
    p[1] = (point){inf, 0};
    p[2] = (point){inf, inf};
    p[3] = (point){0, inf};
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d%d%d", &u[i], &v[i], &w[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                int k = (j + 1) % 4;
                Sline[j] = (line){p[k] - p[j], p[j], p[k]};
            }
            int k = 4;
            bool tmp = false;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    a = 1.0 * (u[i] - u[j]) / (u[i] * u[j]);
                    b = 1.0 * (v[i] - v[j]) / (v[i] * v[j]);
                    c = 1.0 * (w[i] - w[j]) / (w[i] * w[j]);
                    if (pnz(a)) {
                        if (pnz(b))
                            s = (point){0, -c / b}, e = (point){pnz(b), -(a * pnz(b) + c) / b};
                        else s = (point){-c / a, 0}, e = (point){-c / a, -pnz(a)};
                    }
                    else {
                        if (pnz(b))
                            s = (point){0, -c / b}, e = (point){pnz(b), -c / b};
                        else {
                            if (pnz(c) > 0)
                                continue;
                            tmp = true;
                            break;
                        }
                    }
                    Sline[k++] = (line){e - s, s, e};
                }
            }
            if (!tmp && Halfplane(k))
                printf("Yes\n");
            else printf("No\n");
        }
        if (t)
            printf("\n");
    }
    return 0;
}