BZOJ 1035. [ZJOI2008]Risk

#include <bits/stdc++.h>
#define db double

const db eps = 1e-8;
const int N = 2e4 + 7;
const int XN = 1e4;

inline int sign(db x) { return x < -eps ? -1 : x > eps; }
inline int cmp(db x, db y) { return sign(x - y); }

struct P {
    int x, y;
    P(int _x = 0, int _y = 0): x(_x), y(_y) {}
    P operator + (const P &p) const { return {x + p.x, y + p.y}; }
    P operator - (const P &p) const { return {x - p.x, y - p.y}; }
    inline int det(const P &p) { return x * p.y - y * p.x; }
    inline int dot(const P &p) { return x * p.x + y * p.y; }
    inline void read() { scanf("%d%d", &x, &y); }
    int quad() { return y > 0 || (y == 0 && x >= 0); }
} point[N];
std::map<int, int> mp[N * 2];
std::vector<int> nxt[N];
int n, m, point_cnt, country[N];

struct L {
    P st, ed, dir; int x, y;
    L() {}
    L(P st_, P ed_, int x_, int y_) {
        st = st_, ed = ed_, x = x_, y = y_;
        dir = ed - st;
    }
} line[N * 5];
bool agcmp(int x, int y) {
    P p = line[x].dir, q = line[y].dir;
    if (p.quad() != q.quad()) return p.quad() < q.quad();
    return p.det(q) > 0;
}

struct Seg {
    int u, v, type, id;
    Seg() {}
    Seg(int u, int v, int type): u(u), v(v), type(type) {}
    bool operator < (const Seg &p) const {
        if (point[u].x != point[p.u].x) return point[u].x < point[p.u].x;
        return type < p.type;
    }
} seg[N * 5];

struct Cmp {
    bool operator () (const Seg &a, const Seg &b) {
        int aa = (point[b.v] - point[a.u]).det(point[b.u] - point[a.u]),
                bb = (point[b.v] - point[a.v]).det(point[b.u] - point[a.v]);
        int cc = (point[a.v] - point[b.u]).det(point[a.u] - point[b.u]),
                dd = (point[a.v] - point[b.v]).det(point[a.u] - point[b.v]);
        return (aa < 0 && bb <= 0) || (aa <= 0 && bb < 0) || (cc > 0 && dd >= 0) || (cc >= 0 && dd > 0);
    }
};

int getid(int x, int y) {
    x += XN;
    if (mp[x].count(y)) return mp[x][y];
    point[++point_cnt] = P(x - XN, y);
    return mp[x][y] = point_cnt;
}

std::set<Seg, Cmp> st;

bool vis[N];
int mst;

void edit(int id) {
    vis[id] = 1;
    if (point[id].y > point[mst].y || (point[id].y == point[mst].y && point[id].x < point[mst].x))
        mst = id;
    for (int i = 0; i < nxt[id].size(); i++) {
        int x = line[nxt[id][i]].y;
        if (!vis[x]) edit(x);
    }
}

void connect() {
    int cnt = 0;
    for (int i = 1; i <= point_cnt; i++) {
        if (nxt[i].size() && !vis[i]) {
            mst = i;
            edit(i);
            seg[++cnt] = Seg(mst, mst, 2);
        }
    }
    for (int i = 1; i <= m; i++) 
        if (line[i].st.x < line[i].ed.x)
            seg[++cnt] = Seg(line[i].x, line[i].y, 1), seg[++cnt] = Seg(line[i].y, line[i].x, 0);
    std::sort(seg + 1, seg + 1 + cnt);
    for (int i = 1; i <= cnt; i++) {
        if (seg[i].type == 1) {
            st.insert(seg[i]);
        } else if (seg[i].type == 0) {
            st.erase(st.find(Seg(seg[i].v, seg[i].u, 1)));
        } else {
            std::set<Seg, Cmp>::iterator it = st.lower_bound(seg[i]);
            if (it == st.begin()) continue;
            --it;
            int u = it->u, v = seg[i].u;
            line[++m] = L(point[u], point[v], u, v); nxt[u].push_back(m);
            line[++m] = L(point[v], point[u], v, u); nxt[v].push_back(m);
        }
    }
}

int f, out, tag[N];

inline int ops(int x) {
    return (x & 1) ? (x + 1) : (x - 1);
}

void dfs(int index, int id) {
    tag[index] = id;
    int st = line[index].x, ed = line[index].y;
    int area = point[st].det(point[ed]);
    while (st != ed) {
        std::vector<int>::iterator it = std::upper_bound(nxt[ed].begin(), nxt[ed].end(), ops(index), agcmp);
        --it;
        if (it == nxt[ed].begin()) 
            it = nxt[ed].end();
        --it;
        index = *it;
        int j = line[index].y;
        area += point[ed].det(point[j]);
        ed = j;
        tag[index] = id;
    }
    if (area < 0) out = id;
}

int belong[N];
bool G[670][670];

void scanline() {
    st.clear();
    int cnt = 0;
    for (int i = 1; i <= n; i++) 
        seg[++cnt] = Seg(country[i], country[i], 2);
    for (int i = 1; i <= m; i++) 
        if (line[i].st.x < line[i].ed.x)
            seg[++cnt] = Seg(line[i].x, line[i].y, 1), seg[cnt].id = tag[ops(i)], seg[++cnt] = Seg(line[i].y, line[i].x, 0);
    std::sort(seg + 1, seg + 1 + cnt);
    for (int i = 1; i <= cnt; i++) {
        if (seg[i].type == 1) {
            st.insert(seg[i]);
        } else if (seg[i].type == 0) {
            st.erase(st.find(Seg(seg[i].v, seg[i].u, 1)));
        } else {
            std::set<Seg, Cmp>::iterator it = --st.upper_bound(seg[i]);
            belong[seg[i].u] = it->id;
        }
    }
}

int ans[670];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        country[i] = getid(x, y);
    }
    for (int i = 1; i <= m; i++) {
        P a, b;
        a.read(); b.read();
        int x = getid(a.x, a.y), y = getid(b.x, b.y);
        line[i * 2 - 1] = L(a, b, x, y);
        line[i * 2] = L(b, a, y, x);
        nxt[x].push_back(i * 2 - 1); nxt[y].push_back(i * 2);
    }
    m *= 2;
    connect();
    for (int i = 1; i <= point_cnt; i++)
        std::sort(nxt[i].begin(), nxt[i].end(), agcmp);
    for (int i = 1; i <= m; i++)
        if (!tag[i])
            dfs(i, ++f);
    scanline();
    for (int i = 1; i <= m; i += 2) {
        if (tag[i] != out && tag[i + 1] != out)
            G[tag[i]][tag[i + 1]] = G[tag[i + 1]][tag[i]] = 1;
    } 
    for (int i = 1; i <= n; i++) {
        int res = 0;
        for (int j = 1; j <= n; j++) if (i != j && G[belong[country[i]]][belong[country[j]]]) {
            ans[++res] = j;
        }
        printf("%d", res);
        for (int j = 1; j <= res; j++)
            printf(" %d", ans[j]);
        puts("");
    }
    return 0;
}