Tranvick

Untitled

Feb 16th, 2012
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:65777216")
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <cmath>
  9. #include <vector>
  10. #include <set>
  11. #include <stack>
  12. #include <map>
  13. #include <queue>
  14. #include <string>
  15. #include <memory.h>
  16. #include <iterator>
  17. #define mem(A,X) memset(A,X,sizeof(A))
  18. #define memo(A) memset(A,0,sizeof(A))
  19. #define forn(I,B) for (int I=1;I<=(B);I++)
  20. #define forg(H,V) for (int H=first[V];h;h=next[H])
  21. #define rep(I,B) for (int I=0;I<(B);I++)
  22. #define labs(X) (((X)>0)?(X):(-(X)))
  23. #define ropen(X) freopen(X,"r",stdin)
  24. #define wopen(X) freopen(X,"w",stdout)
  25. #define pb push_back
  26. #define mp make_pair
  27. #define all(X) (X).begin(),(X).end()
  28.  
  29. using namespace std;
  30.  
  31. typedef pair <int,int> pii;
  32. typedef pair <long long,long long> pll;
  33. typedef double ld;
  34. typedef long long ll;
  35. typedef vector<int> vi;
  36. const int N=1111;
  37. const int INF=111111111;
  38. const double eps=1e-9;
  39. const double pi=3.14159265358979;
  40.  
  41. struct event{
  42.     int x,y1,y2,type;
  43.     bool operator < (const event & q) const{
  44.         return x<q.x;
  45.     }
  46. } t[N+N];
  47.  
  48. int n,c,curs,co;
  49. ll ans;
  50. vector <pii> a;
  51. vector<pii>::iterator it;
  52.  
  53. int main(){
  54. //  ropen("input.txt");
  55.     scanf("%d",&n);
  56.     forn(i,n){
  57.         int x1,y1,x2,y2;
  58.         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  59.         t[++c]=(event){x1,y2,y1,1};
  60.         t[++c]=(event){x2,y2,y1,-1};
  61.     }      
  62.     sort(t+1,t+c+1);
  63.     forn(i,c){
  64.         ans+=(t[i].x-t[i-1].x)*1ll*curs;
  65.         if (t[i].type==-1){
  66.             for (it=a.begin();it!=a.end();it++)
  67.                 if (it->first==t[i].y1 && it->second==1){
  68.                     a.erase(it);
  69.                     break;
  70.                 }
  71.             for (it=a.begin();it!=a.end();it++)
  72.                 if (it->first==t[i].y2 && it->second==-1){
  73.                     a.erase(it);
  74.                     break;
  75.             }
  76.         } else {
  77.             if (a.size() && a.back().first>=t[i].y1){
  78.                 for (it=a.begin();it!=a.end();it++)
  79.                     if (it->first>=t[i].y1){
  80.                         a.insert(it,mp(t[i].y1,1));
  81.                         break;
  82.                     }
  83.             } else a.pb(mp(t[i].y1,1));
  84.             if (a.size() && a.back().first>=t[i].y2){
  85.                 for (it=a.begin();it!=a.end();it++)
  86.                     if (it->first>=t[i].y2){
  87.                         a.insert(it,mp(t[i].y2,-1));
  88.                         break;
  89.                     }
  90.             } else a.pb(mp(t[i].y2,-1));
  91.         }
  92.         curs=co=0;
  93.         rep(j,a.size()){
  94.             if (co && j) curs+=a[j].first-a[j-1].first;
  95.             co+=a[j].second;
  96.         }
  97.     }
  98.     printf("%I64d\n",ans);
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment