| 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) { |