Salve a tutti.
Mi servirebbe una mano per questo problema (che credevo relativamente semplice).
La mia idea credo sia corretta: elimino le zone pescose che sicuramente non potrò più raggiungere.
Determino le zone da eliminare immaginando dei “rettangoli” che vengono definiti dagli spostamenti a destra (nel caso della prima riga di comandi) e dagli spostamenti in alto (nel caso della seconda riga).
Per aiutarmi a determinare le zone in modo efficiente creo due array delle pescosità: uno ordinato secondo la i e uno ordinato secondo la j.
Lascio il codice che ho scritto (con dei commenti) nella speranza che gli errori derivino da qualche mia svista:
#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;
}
