| 1 | #define MAXN 100100 |
| 2 | struct RMST { |
| 3 | struct point { |
| 4 | int i; ll x, y; |
| 5 | point() : i(-1) { } |
| 6 | ll d1() { return x + y; } |
| 7 | ll d2() { return x - y; } |
| 8 | ll dist(point other) { |
| 9 | return abs(x - other.x) + abs(y - other.y); } |
| 10 | bool operator <(const point &other) const { |
| 11 | return y == other.y ? x > other.x : y < other.y; } |
| 12 | } best[MAXN], arr[MAXN], tmp[MAXN]; |
| 13 | int n; |
| 14 | RMST() : n(0) {} |
| 15 | void add_point(int x, int y) { |
| 16 | arr[arr[n].i = n].x = x, arr[n++].y = y; } |
| 17 | void rec(int l, int r) { |
| 18 | if (l >= r) return; |
| 19 | int m = (l+r)/2; |
| 20 | rec(l,m), rec(m+1,r); |
| 21 | point bst; |
| 22 | for (int i = l, j = m+1, k = l; i <= m || j <= r; k++) { |
| 23 | if (j > r || (i <= m && arr[i].d1() < arr[j].d1())) { |
| 24 | tmp[k] = arr[i++]; |
| 25 | if (bst.i != -1 && (best[tmp[k].i].i == -1 |
| 26 | || best[tmp[k].i].d2() < bst.d2())) |
| 27 | best[tmp[k].i] = bst; |
| 28 | } else { |
| 29 | tmp[k] = arr[j++]; |
| 30 | if (bst.i == -1 || bst.d2() < tmp[k].d2()) |
| 31 | bst = tmp[k]; } } |
| 32 | rep(i,l,r+1) arr[i] = tmp[i]; } |
| 33 | vector<pair<ll,ii> > candidates() { |
| 34 | vector<pair<ll, ii> > es; |
| 35 | rep(p,0,2) { |
| 36 | rep(q,0,2) { |
| 37 | sort(arr, arr+n); |
| 38 | rep(i,0,n) best[i].i = -1; |
| 39 | rec(0,n-1); |
| 40 | rep(i,0,n) { |
| 41 | if(best[arr[i].i].i != -1) |
| 42 | es.push_back({arr[i].dist(best[arr[i].i]), |
| 43 | {arr[i].i, best[arr[i].i].i}}); |
| 44 | swap(arr[i].x, arr[i].y); |
| 45 | arr[i].x *= -1, arr[i].y *= -1; } } |
| 46 | rep(i,0,n) arr[i].x *= -1; } |
| 47 | return es; } }; |
| 48 | // vim: cc=60 ts=2 sts=2 sw=2: |
nothing calls this directly
no outgoing calls
no test coverage detected