Advertisement
Guest User

Untitled

a guest
May 23rd, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAXN 20000
  3. #define MAXP 20000
  4.  
  5. int n, x, y, sol = 0;
  6. struct Point{int x, y, ind;} v[1 + MAXN];
  7. bool cmpX(Point A, Point B){return A.x < B.x || A.x == B.x && A.y < B.y;}
  8. bool cmpY(Point A, Point B){return A.y < B.y || A.y == B.y && A.x < B.x;}
  9. std::vector <Point> px[2 + 2 * MAXP], py[2 + 2 * MAXP];
  10.  
  11. std::vector <int> G[1 + MAXN];
  12. bool foundcycle = 0, seen[1 + MAXN];
  13. void dfs(int node, int dpt){
  14. seen[node] = 1;
  15. if(dpt == n && G[node][0] == 1 || G[node][1] == 1) foundcycle = 1;
  16. if(foundcycle) return;
  17. for(auto y: G[node])
  18. if(!seen[y]) dfs(y, dpt + 1);
  19. }
  20.  
  21. struct Elem{int type, a, b;};
  22. bool cmpEvents(Elem A, Elem B){
  23. int repr1 = v[A.a].y, repr2 = v[B.a].y;
  24. if(A.type == -1) repr1 = v[A.b].y;
  25. if(B.type == -1) repr2 = v[B.b].y;
  26. if(repr1 != repr2) return repr1 < repr2;
  27. return A.type < B.type;
  28. }
  29. std::vector <Elem> Events;
  30.  
  31. #define zeros(x) (x & (-x))
  32. int aib[2 + 2 * MAXP];
  33. inline void update(int pos, int val){
  34. for(int i = pos; i <= 1 + 2 * MAXP; i += zeros(i))
  35. aib[i] += val;
  36. }
  37. inline int query(int pos){
  38. int ans = 0;
  39. for(int i = pos; i > 0; i -= zeros(i))
  40. ans += aib[i];
  41. return ans;
  42. }
  43.  
  44. int main(){
  45. FILE*fi,*fo;
  46. //fi = fopen("a.in","r");
  47. //fo = fopen("a.out","w");
  48. fi = stdin;
  49. fo = stdout;
  50.  
  51. fscanf(fi,"%d", &n);
  52. for(int i = 1; i <= n; i++){
  53. fscanf(fi,"%d%d", &x, &y);
  54. x += 1 + MAXP, y += 1 + MAXP;
  55. v[i] = {x, y, i};
  56. px[x].push_back(v[i]);
  57. py[y].push_back(v[i]);
  58. }
  59.  
  60. for(int i = 1; i <= 2 * MAXP + 1; i++){
  61. if(px[i].size() % 2 == 1 || py[i].size() % 2 == 1){
  62. fprintf(fo,"0");
  63. return 0;
  64. }
  65. std::sort(px[i].begin(), px[i].end(), cmpX);
  66. std::sort(py[i].begin(), py[i].end(), cmpY);
  67. for(int j = 1; j < px[i].size(); j += 2){
  68. G[px[i][j - 1].ind].push_back(px[i][j].ind);
  69. G[px[i][j].ind].push_back(px[i][j - 1].ind);
  70. Events.push_back({-1, px[i][j - 1].ind, px[i][j].ind});
  71. Events.push_back({+1, px[i][j - 1].ind, px[i][j].ind});
  72. sol += px[i][j].y - px[i][j - 1].y;
  73. }
  74. for(int j = 1; j < py[i].size(); j += 2){
  75. G[py[i][j - 1].ind].push_back(py[i][j].ind);
  76. G[py[i][j].ind].push_back(py[i][j - 1].ind);
  77. Events.push_back({0, py[i][j - 1].ind, py[i][j].ind});
  78. sol += py[i][j].x - py[i][j - 1].x;
  79. }
  80. }
  81.  
  82. std::sort(Events.begin(), Events.end(), cmpEvents);
  83. for(auto y: Events){
  84. if(y.type == -1) update(v[y.a].x, -1);
  85. else if(y.type == 0){
  86. if(query(v[y.b].x) - query(v[y.a].x - 1)){
  87. fprintf(fo,"0");
  88. return 0;
  89. }
  90. }
  91. else update(v[y.a].x, 1);
  92. }
  93.  
  94. dfs(1, 1);
  95. if(foundcycle) fprintf(fo,"%d", sol);
  96. else fprintf(fo,"0");
  97.  
  98. return 0;
  99. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement