Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAXN 20000
- #define MAXP 20000
- int n, x, y, sol = 0;
- struct Point{int x, y, ind;} v[1 + MAXN];
- bool cmpX(Point A, Point B){return A.x < B.x || A.x == B.x && A.y < B.y;}
- bool cmpY(Point A, Point B){return A.y < B.y || A.y == B.y && A.x < B.x;}
- std::vector <Point> px[2 + 2 * MAXP], py[2 + 2 * MAXP];
- std::vector <int> G[1 + MAXN];
- bool foundcycle = 0, seen[1 + MAXN];
- void dfs(int node, int dpt){
- seen[node] = 1;
- if(dpt == n && G[node][0] == 1 || G[node][1] == 1) foundcycle = 1;
- if(foundcycle) return;
- for(auto y: G[node])
- if(!seen[y]) dfs(y, dpt + 1);
- }
- struct Elem{int type, a, b;};
- bool cmpEvents(Elem A, Elem B){
- int repr1 = v[A.a].y, repr2 = v[B.a].y;
- if(A.type == -1) repr1 = v[A.b].y;
- if(B.type == -1) repr2 = v[B.b].y;
- if(repr1 != repr2) return repr1 < repr2;
- return A.type < B.type;
- }
- std::vector <Elem> Events;
- #define zeros(x) (x & (-x))
- int aib[2 + 2 * MAXP];
- inline void update(int pos, int val){
- for(int i = pos; i <= 1 + 2 * MAXP; i += zeros(i))
- aib[i] += val;
- }
- inline int query(int pos){
- int ans = 0;
- for(int i = pos; i > 0; i -= zeros(i))
- ans += aib[i];
- return ans;
- }
- int main(){
- FILE*fi,*fo;
- //fi = fopen("a.in","r");
- //fo = fopen("a.out","w");
- fi = stdin;
- fo = stdout;
- fscanf(fi,"%d", &n);
- for(int i = 1; i <= n; i++){
- fscanf(fi,"%d%d", &x, &y);
- x += 1 + MAXP, y += 1 + MAXP;
- v[i] = {x, y, i};
- px[x].push_back(v[i]);
- py[y].push_back(v[i]);
- }
- for(int i = 1; i <= 2 * MAXP + 1; i++){
- if(px[i].size() % 2 == 1 || py[i].size() % 2 == 1){
- fprintf(fo,"0");
- return 0;
- }
- std::sort(px[i].begin(), px[i].end(), cmpX);
- std::sort(py[i].begin(), py[i].end(), cmpY);
- for(int j = 1; j < px[i].size(); j += 2){
- G[px[i][j - 1].ind].push_back(px[i][j].ind);
- G[px[i][j].ind].push_back(px[i][j - 1].ind);
- Events.push_back({-1, px[i][j - 1].ind, px[i][j].ind});
- Events.push_back({+1, px[i][j - 1].ind, px[i][j].ind});
- sol += px[i][j].y - px[i][j - 1].y;
- }
- for(int j = 1; j < py[i].size(); j += 2){
- G[py[i][j - 1].ind].push_back(py[i][j].ind);
- G[py[i][j].ind].push_back(py[i][j - 1].ind);
- Events.push_back({0, py[i][j - 1].ind, py[i][j].ind});
- sol += py[i][j].x - py[i][j - 1].x;
- }
- }
- std::sort(Events.begin(), Events.end(), cmpEvents);
- for(auto y: Events){
- if(y.type == -1) update(v[y.a].x, -1);
- else if(y.type == 0){
- if(query(v[y.b].x) - query(v[y.a].x - 1)){
- fprintf(fo,"0");
- return 0;
- }
- }
- else update(v[y.a].x, 1);
- }
- dfs(1, 1);
- if(foundcycle) fprintf(fo,"%d", sol);
- else fprintf(fo,"0");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement