Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <map>
- #include <cmath>
- #include <ctime>
- #include <string>
- #include <cstring>
- #include <complex>
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- #define mp make_pair
- const double MAGIC = 3;
- const int N = 1 << 17;
- const int C = 503;
- struct Node
- {
- int l, r;
- vector<pii> a;
- Node() : l(), r(), a() {}
- Node(int _l, int _r) : l(_l), r(_r), a() {}
- };
- Node tree[2 * N];
- void build()
- {
- for (int i = 0; i < N; i++)
- tree[N + i] = Node(i, i + 1);
- for (int i = N - 1; i > 0; i--)
- tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r);
- return;
- }
- int n;
- int a[C][C];
- int CNT = 0;
- int ans[N];
- int ANS = 2 * C * C;
- pii all[N];
- void addSegm(int v, int l, int r, pii x)
- {
- if (l <= tree[v].l && tree[v].r <= r)
- {
- tree[v].a.push_back(x);
- return;
- }
- if (l >= tree[v].r || tree[v].l >= r)
- return;
- addSegm(2 * v, l, r, x);
- addSegm(2 * v + 1, l, r, x);
- return;
- }
- bool checkCell(int x, int y)
- {
- if (x < 0 || x >= C || y < 0 || y >= C) return false;
- return a[x][y];
- }
- void addAns(int x, int y)
- {
- for (int dx = 0; dx * dx < ANS; dx++)
- for (int dy = 0;; dy++)
- {
- int d = dx * dx + dy * dy;
- if (d >= ANS) break;
- if (checkCell(x - dx, y - dy) || checkCell(x - dx, y + dy) || checkCell(x + dx, y - dy) || checkCell(x + dx, y + dy))
- {
- ANS = d;
- break;
- }
- }
- }
- int sqr(int x)
- {
- return x * x;
- }
- void addAll(int x, int y)
- {
- for (int i = 0; i < CNT; i++)
- ANS = min(ANS, sqr(x - all[i].first) + sqr(y - all[i].second));
- }
- void dfs(int v)
- {
- if (tree[v].l >= n) return;
- int oldANS = ANS;
- for (pii x : tree[v].a)
- {
- //printf("in %d adding (%d %d)\n", v, x.first, x.second);
- if (ANS * MAGIC < CNT)
- addAns(x.first, x.second);
- else
- addAll(x.first, x.second);
- all[CNT++] = x;
- a[x.first][x.second] = 1;
- }
- if (v >= N)
- {
- ans[v - N] = (CNT >= 2 ? ANS : 0);
- }
- else
- {
- dfs(2 * v);
- dfs(2 * v + 1);
- }
- ANS = oldANS;
- CNT -= (int)tree[v].a.size();
- for (pii x : tree[v].a)
- a[x.first][x.second] = 0;
- return;
- }
- int main()
- {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- for (int i = 0; i < C; i++)
- for (int j = 0; j < C; j++)
- a[i][j] = -1;
- build();
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- {
- char c;
- int x, y;
- scanf(" %c %d%d", &c, &x, &y);
- if (c == '+')
- a[x][y] = i;
- else
- {
- addSegm(1, a[x][y], i, mp(x, y));
- a[x][y] = -1;
- }
- }
- for (int x = 0; x < C; x++)
- for (int y = 0; y < C; y++)
- {
- if (a[x][y] != -1)
- addSegm(1, a[x][y], n, mp(x, y));
- a[x][y] = 0;
- }
- for (int i = 1; i < 2 * N; i++)
- random_shuffle(tree[i].a.begin(), tree[i].a.end());
- dfs(1);
- for (int i = 0; i < n; i++)
- printf("%d\n", ans[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement