Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- /*
- ************************ IDEA ************************
- 1)Elimino tutte le pescosita' che stanno strettamente a SX
- della posizione iniziale
- 2)Prima riga di comandi:
- -Se mi muovo in alto non faccio nulla
- -Se mi muovo verso destra elimino tutti i quadrati pescosi
- che stanno strettamente al disopra del segmento vecchiaPos-nuovaPos
- 3)Elimino tutte le pescisita' che stanno strettamente a DX
- della posizione finale e strettamente in basso alla posizione iniziale
- 4)Seconda riga di comandi:
- -Se mi muovo in alto elimino tutti i quadrati pescosi
- che stanno strettamente a destra del segmento vecchiaPos-nuovaPos
- -Se mi muovo verso destra non faccio nulla
- 5)Conto quante pescosita' mi sono rimaste, stampo e chiudo
- */
- const int MAXP=1000005;
- struct MAT{
- int i, j, pos;
- }Pi[MAXP], Pj[MAXP], att, start, end;
- int P, c;
- bool occ[MAXP];
- bool cmp1(const MAT&, const MAT&);
- bool cmp2(const MAT&, const MAT&);
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- //Salvo . . .
- scanf("%d %d %d", &P, &start.i, &start.j);
- att=start;
- for(int i=0; i<P; i++){
- scanf("%d %d", &(Pj[i].i), &(Pj[i].j));
- Pi[i]=Pj[i];
- Pi[i].pos=Pj[i].pos=i;
- }
- //Ordino . . .
- sort(Pi,Pi+P,cmp1);
- sort(Pj,Pj+P,cmp2);
- int h;
- //Elimino a SX della casella A . . .
- for(h=0; h<P && Pi[h].i<att.i; h++)
- occ[ Pi[h].pos ]=true;
- //Prima riga di comandi . . .
- do{
- scanf("%d", &c);
- if(c>0) att.j+=c;
- else{
- att.i-=c;
- while(h<P && Pi[h].i<att.i){
- if(Pi[h].j>att.j)
- occ[ Pi[h].pos ]=true;
- h++;
- }
- }
- }while(c!=0);
- //Elimino la striscia sopra alla casella B
- //e tutto cio' che gli sta a DX . . .
- for(h; h<P; h++)
- if(Pi[h].i>att.i || (Pi[h].i==att.i && Pi[h].j>att.j))
- occ[ Pi[h].pos ]=true;
- //Riparto da A . . .
- att=start;
- //Elimino tutto cio' che e' al disotto della casella A . . .
- for(h=0; h<P && Pj[h].j<att.j; h++)
- occ[ Pj[h].pos ]=true;
- //Seconda riga di comandi . . .
- do{
- scanf("%d", &c);
- if(c>0){
- att.j+=c;
- while(h<P && Pj[h].j<att.j){
- if(Pj[h].i>att.i)
- occ[ Pj[h].pos ]=true;
- h++;
- }
- }
- else att.i-=c;
- }while(c!=0);
- //Non serve inizializzare c, e' gia' a zero.
- //Conto le caselle pescose che si sono "salvate" . . .
- for(h=0; h<P; h++)
- if(!occ[h])
- c++;
- //Stampo e ciao! :D
- printf("%d\n", c);
- return 0;
- }
- bool cmp1(const MAT &m1, const MAT &m2)
- {
- if(m1.i!=m2.i) return m1.i<m2.i;
- return m1.j>m2.j;
- }
- bool cmp2(const MAT &m1, const MAT &m2)
- {
- if(m1.j!=m2.j) return m1.j<m2.j;
- return m1.i>m2.i;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement