POJ 1755 Triathlon 半平面交

看的这里：http://blog.csdn.net/non_cease/article/details/7820361

题意：铁人三项比赛，给出ｎ个人进行每一项的速度vi, ui, wi; 对每个人判断，通过改变3项比赛的路程，是否能让该人获胜（严格获胜）。

思路：题目实际上是给出了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 ， 这样就化三维为二维，可用半平面交判断是否存在解了，

对每个人构造一次，求一次半平面交即可。

关键是根据这个斜率式子怎么搞成向量的。需要想一想。

然后注意的是半平面交出来是单独一个点是不行的。

因为题目要求的是严格胜出

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#include <sstream>#include <queue>#include <vector>#define MAXN 111111#define MAXM 211111#define PI acos(-1.0)#define eps 1e-8#define INF 1e10using namespace std;int dblcmp(double d){    if (fabs(d) < eps) return 0;    return d > eps ? 1 : -1;}struct point{    double x, y;    point(){}    point(double _x, double _y):    x(_x), y(_y){};    void input()    {        scanf("%lf%lf",&x, &y);    }    double dot(point p)    {        return x * p.x + y * p.y;    }    double distance(point p)    {        return hypot(x - p.x, y - p.y);    }    point sub(point p)    {        return point(x - p.x, y - p.y);    }    double det(point p)    {        return x * p.y - y * p.x;    }    bool operator == (point a)const    {        return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;    }    bool operator < (point a)const    {        return dblcmp(a.x - x) == 0 ? dblcmp(y - a.y) < 0 : x < a.x;    }}p[MAXN];struct line{    point a,b;    line(){}    line(point _a,point _b)    {        a=_a;        b=_b;    }    bool parallel(line v)    {        return dblcmp(b.sub(a).det(v.b.sub(v.a))) == 0;    }    point crosspoint(line v)    {        double a1 = v.b.sub(v.a).det(a.sub(v.a));        double a2 = v.b.sub(v.a).det(b.sub(v.a));        return point((a.x * a2 - b.x * a1) / (a2 - a1), (a.y * a2 - b.y * a1) / (a2 - a1));    }    bool operator == (line v)const    {    return (a == v.a) && (b == v.b);    }};struct halfplane:public line{double angle;halfplane(){}//表示向量 a->b逆时针(左侧)的半平面halfplane(point _a, point _b){a = _a;b = _b;}halfplane(line v){a = v.a;b = v.b;}void calcangle(){angle = atan2(b.y - a.y, b.x - a.x);}bool operator <(const halfplane &b)const{return dblcmp(angle - b.angle) < 0;}};struct polygon{    int n;    point p[MAXN];    line l[MAXN];    double area;    void getline()    {        for (int i = 0; i < n; i++)        {            l[i] = line(p[i], p[(i + 1) % n]);        }    }    void getarea()    {        area = 0;        int a = 1, b = 2;        while(b <= n - 1)        {            area += p[a].sub(p[0]).det(p[b].sub(p[0]));            a++;            b++;        }        area = fabs(area) / 2;    }}convex;bool judge(point a, point b, point o){    return dblcmp(a.sub(o).det(b.sub(o))) <= 0; //此处有等于号代表的是求出的半平面交为一个点不合法，去掉等于号则代表交成一个点也行}struct halfplanes{int n;halfplane hp[MAXN];point p[MAXN];int que[MAXN];int st, ed;void push(halfplane tmp){hp[n++] = tmp;}void unique(){int m = 1, i;for (i = 1; i < n;i++){if (dblcmp(hp[i].angle - hp[i - 1].angle))hp[m++] = hp[i];else if (dblcmp(hp[m - 1].b.sub(hp[m - 1].a).det(hp[i].a.sub(hp[m - 1].a)) > 0))hp[m - 1] = hp[i];}n = m;}bool halfplaneinsert(){int i;for (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 (i = 2; i < n; i++){while (st < ed && judge(hp[i].b, p[ed], hp[i].a)) ed--;while (st < ed && judge(hp[i].b, p[st + 1], hp[i].a)) 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 && judge(hp[que[st]].b, p[ed], hp[que[st]].a)) ed--;while (st < ed && judge(hp[que[ed]].b, p[st + 1], hp[que[ed]].a)) 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;int j = st, i = 0;for (; j <= ed; i++, j++){con.p[i] = p[j];}}}h;int A[MAXN], B[MAXN], C[MAXN];int n;int main(){    double xa, xb, ya, yb;    scanf("%d", &n);    for(int i = 0; i < n; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);    for(int i = 0; i < n; i++)    {        int flag = 0;        h.n = 0;        h.push(halfplane(point(0, 0), point(INF, 0)));        h.push(halfplane(point(INF, 0), point(INF, INF)));        h.push(halfplane(point(INF, INF), point(0, INF)));        h.push(halfplane(point(0, INF), point(0, 0)));        for(int j = 0; j < n; j++)        {            if(j == i) continue;            double a = 1.0 / A[j] - 1.0 / A[i];            double b = 1.0 / B[j] - 1.0 / B[i];            double c = 1.0 / C[j] - 1.0 / C[i];            int d1 = dblcmp(a);            int d2 = dblcmp(b);            int d3 = dblcmp(c);            if(!d1)            {                if(!d2)                {                    if(d3 <= 0)                    {                        flag = 1;                        break;                    }                    continue;                }                xa = 0, xb = d2;                ya = yb = -c / b;            }            else            {                if(!d2)                {                    xa = xb = -c / a;                    ya = 0, yb = -d1;                }                else                {                    xa = 0;                    ya = -c / b;                    xb = d2;                    yb = -(c + a * xb) / b;                }            }            h.push(halfplane(point(xa, ya), point(xb, yb)));        }        if(flag || !h.halfplaneinsert() ) puts("No");        else puts("Yes");    }    return 0;}