Advertisement
Guest User

Untitled

a guest
Sep 6th, 2014
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. /*
  5. ************************ IDEA ************************
  6. 1)Elimino tutte le pescosita' che stanno strettamente a SX
  7.   della posizione iniziale
  8.  
  9. 2)Prima riga di comandi:
  10. -Se mi muovo in alto non faccio nulla
  11. -Se mi muovo verso destra elimino tutti i quadrati pescosi
  12.  che stanno strettamente al disopra del segmento vecchiaPos-nuovaPos
  13.  
  14. 3)Elimino tutte le pescisita' che stanno strettamente a DX
  15.   della posizione finale e strettamente in basso alla posizione iniziale
  16.  
  17. 4)Seconda riga di comandi:
  18. -Se mi muovo in alto elimino tutti i quadrati pescosi
  19.  che stanno strettamente a destra del segmento vecchiaPos-nuovaPos
  20. -Se mi muovo verso destra non faccio nulla
  21.  
  22. 5)Conto quante pescosita' mi sono rimaste, stampo e chiudo
  23.  
  24. */
  25.  
  26. const int MAXP=1000005;
  27.  
  28. struct MAT{
  29.     int i, j, pos;
  30. }Pi[MAXP], Pj[MAXP], att, start, end;
  31.  
  32. int P, c;
  33. bool occ[MAXP];
  34.  
  35. bool cmp1(const MAT&, const MAT&);
  36. bool cmp2(const MAT&, const MAT&);
  37.  
  38. int main()
  39. {
  40.     freopen("input.txt","r",stdin);
  41.     freopen("output.txt","w",stdout);
  42.    
  43.     //Salvo . . .
  44.     scanf("%d %d %d", &P, &start.i, &start.j);
  45.     att=start;
  46.     for(int i=0; i<P; i++){
  47.         scanf("%d %d", &(Pj[i].i), &(Pj[i].j));
  48.         Pi[i]=Pj[i];
  49.         Pi[i].pos=Pj[i].pos=i;
  50.     }
  51.      //Ordino . . .
  52.     sort(Pi,Pi+P,cmp1);
  53.     sort(Pj,Pj+P,cmp2);
  54.    
  55.     int h;
  56.    
  57.     //Elimino a SX della casella A . . .
  58.     for(h=0; h<P && Pi[h].i<att.i; h++)
  59.              occ[ Pi[h].pos ]=true;
  60.    
  61.     //Prima riga di comandi . . .
  62.     do{
  63.         scanf("%d", &c);
  64.         if(c>0) att.j+=c;
  65.         else{
  66.             att.i-=c;
  67.             while(h<P && Pi[h].i<att.i){
  68.                 if(Pi[h].j>att.j)
  69.                          occ[ Pi[h].pos ]=true;
  70.                 h++;
  71.             }
  72.         }
  73.     }while(c!=0);
  74.    
  75.     //Elimino la striscia sopra alla casella B
  76.     //e tutto cio' che gli sta a DX . . .
  77.     for(h; h<P; h++)
  78.         if(Pi[h].i>att.i || (Pi[h].i==att.i && Pi[h].j>att.j))
  79.             occ[ Pi[h].pos ]=true;
  80.    
  81.     //Riparto da A . . .
  82.     att=start;
  83.    
  84.     //Elimino tutto cio' che e' al disotto della casella A . . .
  85.     for(h=0; h<P && Pj[h].j<att.j; h++)
  86.              occ[ Pj[h].pos ]=true;
  87.    
  88.     //Seconda riga di comandi . . .
  89.     do{
  90.         scanf("%d", &c);
  91.         if(c>0){
  92.             att.j+=c;
  93.             while(h<P && Pj[h].j<att.j){
  94.                 if(Pj[h].i>att.i)
  95.                          occ[ Pj[h].pos ]=true;
  96.                 h++;
  97.             }
  98.         }
  99.         else att.i-=c;
  100.     }while(c!=0);
  101.    
  102.     //Non serve inizializzare c, e' gia' a zero.
  103.     //Conto le caselle pescose che si sono "salvate" . . .
  104.     for(h=0; h<P; h++)
  105.              if(!occ[h])
  106.                  c++;
  107.    
  108.     //Stampo e ciao! :D
  109.     printf("%d\n", c);
  110.    
  111.     return 0;
  112. }
  113.  
  114. bool cmp1(const MAT &m1, const MAT &m2)
  115. {
  116.     if(m1.i!=m2.i) return m1.i<m2.i;
  117.     return m1.j>m2.j;
  118. }
  119.  
  120. bool cmp2(const MAT &m1, const MAT &m2)
  121. {
  122.     if(m1.j!=m2.j) return m1.j<m2.j;
  123.     return m1.i>m2.i;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement