BZOJ3190 [JLOI2013]赛车
Solution
这个变态题!!!
本来准备写一个显然的半平面交(同水平可见直线)简单练手,然后就被恶心到了!!!
//其实这道题暴力或者单调栈也能过。
看第二组测试数据:
Input:
5
1 1 0 0 0
15 16 10 20 20
Output:
4
1 2 4 5
Code
#include <bits/stdc++.h> using namespace std; #define N 10005 #define sqr(x) ((x) * (x)) #define dcmp(x) (fabs(x) < 1e-20) struct point { long double x, y; point(long double _x = 0.0, long double _y = 0.0) : x(_x), y(_y) {} point operator +(const point &a) const { return point(x + a.x, y + a.y); } point operator -(const point &a) const { return point(x - a.x, y - a.y); } point operator *(long double a) { return point(x * a, y * a); } friend long double cross(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } friend long double dist(const point &a, const point &b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); } friend ostream &operator <<(ostream &out, const point &a) { out << '(' << a.x << ',' << a.y << ')'; return out; } }; struct line { int id; point p, v; long double t; line() {} line(int _id, point _p, point _v) : id(_id), p(_p), v(_v) { t = atan2(v.y, v.x); } inline bool operator <(const line &a) const { return t < a.t; } friend bool left(const point &p, const line &l) { return cross(l.v, p - l.p) >= 0; } friend point intersection(line a, line b) { return a.p + a.v * (cross(b.v, a.p - b.p) / cross(a.v, b.v)); } }; int n, a[N], b[N], ans[N], head, tail; point vertex[N]; line l[N], deq[N]; void half_plane_intersection(int tot) { sort(l + 1, l + tot + 1); head = tail = 0; deq[tail++] = l[1]; for (int i = 2; i <= tot; ++i) { if (l[i].p.y == deq[tail - 1].p.y && l[i].v.y == deq[tail - 1].v.y) { deq[tail++] = l[i]; vertex[tail - 1] = vertex[tail - 2]; continue; } while (tail - head >= 2 && !left(vertex[tail - 1], l[i])) --tail; while (tail - head >= 2 && !left(vertex[head + 1], l[i])) ++head; if (!dcmp(l[i].t - deq[tail - 1].t)) deq[tail++] = l[i]; else if (left(l[i].p, deq[tail - 1])) deq[tail - 1] = l[i]; if (tail - head >= 2) vertex[tail - 1] = intersection(deq[tail - 2], deq[tail - 1]); } while (tail - head >= 2 && !left(vertex[tail - 1], deq[head])) --tail; vertex[head] = intersection(deq[tail - 1], deq[head]); } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch-'0'; ch = getchar(); } return x * f; } int main() { cin >> n; for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= n; ++i) b[i] = read(); for (int i = 1; i <= n; ++i) l[i] = line(i, point(0, a[i]), point(1, b[i])); half_plane_intersection(n); while (vertex[head + 1].x < 0) ++head; for (int i = head; i <= tail - 1; ++i) ans[++ans[0]] = deq[i].id; sort(ans + 1, ans + ans[0] + 1); cout << ans[0] << endl; for (int i = 1; i < ans[0]; ++i) printf("%d ", ans[i]); cout << ans[ans[0]]; return 0; }