#include <cstdio> #include <vector> #include <algorithm> //Brutalnie O(n^2) using namespace std; const int maxn=50000; int wys[maxn]; int poz1[maxn]; int poz2[maxn]; struct sam { int wys; int poz1; int poz2; }; sam tsam[maxn]; bool porzw(int a,int b) {return tsam[a].wys<tsam[b].wys;} bool porz1(int a,int b) {return tsam[a].poz1<tsam[b].poz1;} bool porz2(int a,int b) {return tsam[a].poz2<tsam[b].poz2;} int main () { int t,n,w; int x1,y1,x2,y2; int s,st; bool ok=true; scanf("%d ",&t); while(t--) { ok=true; scanf("%d %d",&n,&w); for (int i=0;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); /*wys[i]=y2-y1; porz1[i]=make_pair(x1,i);*/ tsam[i].wys=y2-y1; tsam[i].poz1=x1; wys[i]=poz1[i]=poz2[i]=i; } for (int i=0;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); tsam[i].poz2=x1; } //sort(wys,wys+n,porzw); sort(poz1,poz1+n,porz1); sort(poz2,poz2+n,porz2); for (int i=0;i<n;i++) {tsam[poz1[i]].poz1=i;tsam[poz2[i]].poz2=i;} //ustawiam im pozycje zamiast wspolrzednych for (int i=0;i<n&&ok;i++) { s=poz2[i]; if (tsam[s].poz2<tsam[s].poz1) //samochod przeparkowany z prawej na lewo // musze teraz sprawdzic wszystkie ktore w starym porzadku lezaly przed nim bo tylko one kolidowaly for (int k=0;k<tsam[s].poz1&&ok;k++) { st=poz1[k];//porownywany samochod if(w-tsam[s].wys<tsam[st].wys && tsam[st].poz2>tsam[s].poz2) ok=false; } } if (ok)printf("TAK\n");else printf("NIE\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <cstdio> #include <vector> #include <algorithm> //Brutalnie O(n^2) using namespace std; const int maxn=50000; int wys[maxn]; int poz1[maxn]; int poz2[maxn]; struct sam { int wys; int poz1; int poz2; }; sam tsam[maxn]; bool porzw(int a,int b) {return tsam[a].wys<tsam[b].wys;} bool porz1(int a,int b) {return tsam[a].poz1<tsam[b].poz1;} bool porz2(int a,int b) {return tsam[a].poz2<tsam[b].poz2;} int main () { int t,n,w; int x1,y1,x2,y2; int s,st; bool ok=true; scanf("%d ",&t); while(t--) { ok=true; scanf("%d %d",&n,&w); for (int i=0;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); /*wys[i]=y2-y1; porz1[i]=make_pair(x1,i);*/ tsam[i].wys=y2-y1; tsam[i].poz1=x1; wys[i]=poz1[i]=poz2[i]=i; } for (int i=0;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); tsam[i].poz2=x1; } //sort(wys,wys+n,porzw); sort(poz1,poz1+n,porz1); sort(poz2,poz2+n,porz2); for (int i=0;i<n;i++) {tsam[poz1[i]].poz1=i;tsam[poz2[i]].poz2=i;} //ustawiam im pozycje zamiast wspolrzednych for (int i=0;i<n&&ok;i++) { s=poz2[i]; if (tsam[s].poz2<tsam[s].poz1) //samochod przeparkowany z prawej na lewo // musze teraz sprawdzic wszystkie ktore w starym porzadku lezaly przed nim bo tylko one kolidowaly for (int k=0;k<tsam[s].poz1&&ok;k++) { st=poz1[k];//porownywany samochod if(w-tsam[s].wys<tsam[st].wys && tsam[st].poz2>tsam[s].poz2) ok=false; } } if (ok)printf("TAK\n");else printf("NIE\n"); } return 0; } |