Advertisement
Guest User

Windows

a guest
Oct 13th, 2011
488
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1.  #include <cstdio>
  2.  #include <vector>
  3.  #include <algorithm>
  4.  
  5.  using namespace std;
  6.  
  7.  struct xseg {int x,miny,maxy; bool open;};
  8.  struct yseg {int y,wx1,wx2; bool down;};
  9.  
  10.  vector <xseg> dx;
  11.  vector <yseg> dy;
  12.  vector <int> t;
  13.  vector <int> tmax;
  14.  vector <int> wmax;
  15.  bool com(yseg a,yseg b) {
  16.      return a.y<b.y;}
  17.  bool com1(xseg a,xseg b) {
  18.     if (a.x!=b.x) return a.x<b.x;
  19.     if (a.open) return true;
  20.     return false;}
  21.  int min (int a,int b) {return (a<b?a:b);}
  22.  int max (int a,int b) {return (a>b?a:b);}
  23.  int n;
  24.  
  25.  
  26.  void update(int v,int tL,int tR,int l,int r,int add){
  27.     if (l>r) return;
  28.     if (tR==tL|(tL==l&tR==r)) {t[v]+=add;tmax[v]+=add;return;}
  29.     int tM=(tL+tR)/2;
  30.     update(v*2,tL,tM,l,min(r,tM),add);
  31.     update(v*2+1,tM+1,tR,max(l,tM+1),r,add);
  32.     tmax[v]=-1;
  33.     if (tmax[v]<tmax[v*2+1]) {tmax[v]=tmax[v*2+1]+t[v];wmax[v]=wmax[v*2+1];}
  34.     if (tmax[v]<tmax[v*2]) {tmax[v]=tmax[v*2]+t[v];wmax[v]=wmax[v*2];}
  35.  }
  36.  
  37.  pair <int,int> getmax() {
  38.     return make_pair(tmax[1],wmax[1]);
  39.  }
  40.  
  41.  
  42.  
  43.  int main() {
  44.      freopen("windows.in","r",stdin);
  45.      //freopen("windows.out","w",stdout);
  46.      scanf("%d\n",&n);
  47.      for (int i=1;i<=n;i++)
  48.      {
  49.       int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
  50.       xseg z; z.x=x1; z.open=true;
  51.       dx.push_back(z);
  52.       z.x=x2; z.open=false;
  53.       dx.push_back(z);
  54.       yseg v; v.y=y1; v.down=true; v.wx1=(int)dx.size()-1; v.wx2=v.wx1-1;
  55.       dy.push_back(v);
  56.       v.y=y2; v.down=false; v.wx1=(int)dx.size()-1; v.wx2=v.wx1-1;
  57.       dy.push_back(v);
  58.      }
  59.      sort(dy.begin(),dy.end(),com);
  60.      
  61.      int down[dy.size()]; int up[dy.size()];
  62.      down[0]=0;
  63.      for (int i=1;i<(int)dy.size();i++)
  64.          if (dy[i].y==dy[i-1].y) down[i]=down[i-1]; else down[i]=i;
  65.      up[dy.size()-1]=dy.size()-1;
  66.      for (int i=(int)dy.size()-2;i>=0;i--)
  67.          if (dy[i].y==dy[i+1].y) up[i]=up[i+1]; else up[i]=i;
  68.      
  69.    
  70.      for (int i=0;i<(int)dy.size();i++)
  71.       if (dy[i].down) {dx[dy[i].wx1].miny=down[i]; dx[dy[i].wx2].miny=down[i];}
  72.        else {dx[dy[i].wx1].maxy=up[i]; dx[dy[i].wx2].maxy=up[i];}
  73.      sort(dx.begin(),dx.end(),com1);
  74.      //подготовка
  75.  
  76.      int p[30]; p[0]=1;
  77.      for (int i=1;i<=30;i++)
  78.       { p[i]=p[i-1]*2; if (p[i]>=(int)dy.size()) {n=p[i];break;} }
  79.      t.resize(2*n+3,0); tmax.resize(2*n+3,0); wmax.resize(2*n+3);//n до степени 2-ки
  80.      for (int i=n;i<=2*n-1;i++) wmax[i]=i;
  81.      for (int i=1;i<n;i++) wmax[i]=wmax[2*i];
  82.      
  83.     // for (int i=0;i<(int)dx.size();i++)
  84.     //  printf("%d to %d = %d\n",dx[i].miny+n,dx[i].maxy+n,dx[i].open);
  85.      
  86.      int xm,ym,max=-1;
  87.      for (int i=0;i<(int)dx.size();i++)
  88.      { int add; if (dx[i].open) add=1; else add=-1;
  89.        update(1,n,2*n-1,dx[i].miny+n,dx[i].maxy+n,add);
  90.        pair <int,int> k=getmax();
  91.        if (k.first>max) {xm=dx[i].x;ym=dy[k.second-n].y;max=k.first;}
  92.          
  93.             // for (int j=dx[i].miny;j<=dx[i].maxy;j++)
  94.            //  {t[j]+=add; if (t[j]>max) {xm=dx[i].x;ym=dy[j].y; max=t[j];}}
  95.        // printf("getmax=%d\n",getmax().first);
  96.       // for (int j=1;j<=2*n-1;j++) printf("t[%d]=%d tmax[%d]=%d wmax[%d]=%d\n",j,t[j],j,tmax[j],j,wmax[j]);
  97.      // printf("\n");
  98.      }
  99.      printf("%d\n%d %d",max,xm,ym);
  100.      return 0;
  101. }
  102.  
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement