BZOJ3190 [JLOI2013]赛车

2015.01.23 09:52 Fri| 1 visits oi_2015| 2015_刷题日常| Text

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;
}