Submission #1190213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190213		omsincoconut	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3097 ms	99672 KiB

circle_selection

/*
A circle (x1, y1, r1) intersects (x2, y2, r2) if and only if

sqrt((x1-x2)^2 + (y1-y2)^2) <= r1+r2
(x1-x2)^2 + (y1-y2)^2 <= (r1+r2)^2
(x1-x2)^2 + (y1-y2)^2 - (r1+r2)^2 <= 0
x1^2 - 2x1x2 + x2^2 + y1^2 - 2y1y2 + y2^2 - r1^2 + 2r1r2 - r2^2 <= 0
(x1^2 + y1^2 - r1^2) + -2x2(x1) - 2y2(y1) + 2r2(r1) + (x2^2 + y2^2 - r2^2) <= 0

Sub 1, brute force

Sub 2
Assume x1 >= x2
(x1-x2)^2 <= (r1+r2)^2
x1-x2 <= r1-r2
r2-x2 <= x1+r1
(Sort by r-x, sweepline by x)

Sub 4, Proof by AC
The condition reduces to finding all points inside a circle (x, y, 2r).
Consider instead the square bounded by ([x-2r, x+2r], [y-2r, y+2r]).
Check every point in the square, then erase all that is in the circle.

Full soln, Proof by AC
Code Sub 4 soln in such a way that it also supports a more general case.

Until 3:40 left, code this
*/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXN = 3e5+5;

int n;
ll x[MAXN], y[MAXN], r[MAXN];

int ord_r[MAXN];
bool sort_by_r(int a, int b) {
    return (r[a] != r[b]) ? (r[a] > r[b]) : (a < b);
}

int ord_xy[MAXN];
bool sort_by_xy(int a, int b) {
    if (x[a] != x[b]) return x[a] < x[b];
    if (y[a] != y[b]) return y[a] < y[b];
    if (r[a] != r[b]) return r[a] > r[b];
    return a < b;
}

// Persistent segment tree
namespace pers{
    vector<int> tree, lchild, rchild;

    int newnode(int val = 0, int lc = -1, int rc = -1) {
        tree.push_back(val);
        lchild.push_back(lc);
        rchild.push_back(rc);
        return tree.size()-1;
    }
    
    int init(int l = 0, int r = MAXN) {
        if (l == r) {
            int nn = newnode();
            return nn;
        }
    
        int mid = (l+r)>>1;
        int lc = init(l, mid), rc = init(mid+1, r);
        int nn = newnode(0, lc, rc);
    
        return nn;
    }
    
    int update(int v, int p, int x, int tl = 0, int tr = MAXN) {
        if (tl == tr) {
            int nn = newnode(tree[v]+x);
            return nn;
        }
    
        int mid = (tl+tr)>>1, lc = lchild[v], rc = rchild[v];
        if (p <= mid) {
            int nn = update(lc, p, x, tl, mid);
            lc = nn;
        }  else {
            int nn = update(rc, p, x, mid+1, tr);
            rc = nn;
        }
    
        int rnn = newnode(tree[lc] + tree[rc], lc, rc);
        return rnn;
    }
    
    int query(int v, int l, int r, int tl = 0, int tr = MAXN) {
        if (l <= tl && tr <= r) return tree[v];
        if (r < tl || tr < l) return 0;
    
        int mid = (tl+tr)>>1, lc = lchild[v], rc = rchild[v];
    
        return query(lc, l, r, tl, mid) + query(rc, l, r, mid+1, tr);
    }
}

using namespace pers;

int roots[MAXN];

ll xs[MAXN], ys[MAXN];

void generate_coordcompression(ll *a, ll *as) {
    for (int i = 1; i <= n; i++) {
        as[i] = a[i];
    }
    as[0] = -2e9;
    sort(as, as+n+1);
}

int yid(int y) {
    return lower_bound(ys, ys+n+1, y) - ys;
}

int nextpt(int cur, int yl, int yr) {
    if (yl > yr) return n+1;

    int cs = query(roots[cur], yl, yr);

    int l = cur, r = n+1;
    while (r-l > 1) {
        int mid = (l+r)>>1;
        int ms = query(roots[mid], yl, yr);
        if (ms > cs) r = mid;
        else l = mid;
    }

    return r;
}

vector<int> getid(int xl, int xr, int yl, int yr) {
    xl = lower_bound(xs, xs+n+1, xl) - xs;
    xr = upper_bound(xs, xs+n+1, xr) - xs - 1;
    yl = lower_bound(ys, ys+n+1, yl) - ys;
    yr = upper_bound(ys, ys+n+1, yr) - ys - 1;

    int curx = max(0, xl-1);
    vector<int> ret;
    while (true) {
        curx = nextpt(curx, yl, yr);
        if (curx > xr) return ret;
        ret.push_back(ord_xy[curx]);
    }
}

int ans[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }

    iota(ord_r+1, ord_r+n+1, 1);
    sort(ord_r+1, ord_r+n+1, sort_by_r);
    iota(ord_xy+1, ord_xy+n+1, 1);
    sort(ord_xy+1, ord_xy+n+1, sort_by_xy);

    generate_coordcompression(x, xs);
    generate_coordcompression(y, ys);

    roots[0] = init();
    for (int i = 1; i <= n; i++) {
        roots[i] = update(roots[i-1], yid(y[ord_xy[i]]), 1);
    }

    fill(ans, ans+n+1, -1);

    for (int i = 1; i <= n; i++) {
        int curc = ord_r[i];
        if (ans[curc] != -1) continue;
        ans[curc] = curc;

        vector<int> id = getid(x[curc] - 2*r[curc], x[curc] + 2*r[curc], y[curc] - 2*r[curc], y[curc] + 2*r[curc]);
        for (int j : id) {
            if (ans[j] == -1 && (x[curc]-x[j])*(x[curc]-x[j]) + (y[curc]-y[j])*(y[curc]-y[j]) <= (r[curc]+r[j])*(r[curc]+r[j])) {
                ans[j] = curc;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";

    return 0;
}

/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13