POJ 1755 Triathlon 半平面交
题意:铁人三项比赛,给出n个人进行每一项的速度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 1e10 using 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; }
补充:软件开发 , C++ ,