#include<cstdio> #include<algorithm> using namespace std; struct glass{ long long int w_min; long long int w_max; long long int h_min; long long int h_max; }; bool por(glass a, glass b){ if(a.w_min<b.w_min)return true; if(a.w_min>b.w_min)return false; if(a.w_max<b.w_max)return true; if(a.w_max>b.w_max)return false; if(a.h_min<b.h_min)return true; if(a.h_min>b.h_min)return false; if(a.h_max<b.h_max)return true; if(a.h_max>b.h_max)return false; } glass szyba[100001]; int za_malo_czasu_by_pisac_binary_searcha(int value, int start, int end, int typ){ for(int i=start; i<end; ++i){ if(typ==1 && szyba[i].w_min>value)return i; if(typ==2 && szyba[i].w_max==value)return i; if(typ==3 && szyba[i].h_min>value)return i; if(typ==4 && szyba[i].h_max==value)return i; if(i==(end-1) && (typ==1 || typ==3))return end; if(i==(end-1) && (typ==2 || typ==4))return end+1; } } glass maj; int t,n,poczatek,koniec; int main(){ scanf("%d",&t); for(int test=0; test<t; ++test){ scanf("%d",&n); //Wielkie czyszczenie zmiennych maj.w_min=1000000033; maj.w_max=0; maj.h_min=1000000033; maj.h_max=0; poczatek=0; koniec=n; //koniec czyszczenia for(int i=0; i<n; ++i){ scanf("%lld %lld %lld %lld", &szyba[i].w_min, &szyba[i].w_max, &szyba[i].h_min, &szyba[i].h_max); if(szyba[i].w_min<maj.w_min)maj.w_min=szyba[i].w_min; if(szyba[i].w_max>maj.w_max)maj.w_max=szyba[i].w_max; if(szyba[i].h_min<maj.h_min)maj.h_min=szyba[i].h_min; if(szyba[i].h_max>maj.h_max)maj.h_max=szyba[i].h_max; } sort(szyba,szyba+n,por); koniec=za_malo_czasu_by_pisac_binary_searcha(maj.w_min,poczatek,koniec,1); poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.w_max,poczatek,koniec,2); koniec=za_malo_czasu_by_pisac_binary_searcha(maj.h_min,poczatek,koniec,3); poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.h_max,poczatek,koniec,4); if(koniec<=poczatek){ printf("NIE\n"); continue; } printf("TAK\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 70 71 72 73 74 75 | #include<cstdio> #include<algorithm> using namespace std; struct glass{ long long int w_min; long long int w_max; long long int h_min; long long int h_max; }; bool por(glass a, glass b){ if(a.w_min<b.w_min)return true; if(a.w_min>b.w_min)return false; if(a.w_max<b.w_max)return true; if(a.w_max>b.w_max)return false; if(a.h_min<b.h_min)return true; if(a.h_min>b.h_min)return false; if(a.h_max<b.h_max)return true; if(a.h_max>b.h_max)return false; } glass szyba[100001]; int za_malo_czasu_by_pisac_binary_searcha(int value, int start, int end, int typ){ for(int i=start; i<end; ++i){ if(typ==1 && szyba[i].w_min>value)return i; if(typ==2 && szyba[i].w_max==value)return i; if(typ==3 && szyba[i].h_min>value)return i; if(typ==4 && szyba[i].h_max==value)return i; if(i==(end-1) && (typ==1 || typ==3))return end; if(i==(end-1) && (typ==2 || typ==4))return end+1; } } glass maj; int t,n,poczatek,koniec; int main(){ scanf("%d",&t); for(int test=0; test<t; ++test){ scanf("%d",&n); //Wielkie czyszczenie zmiennych maj.w_min=1000000033; maj.w_max=0; maj.h_min=1000000033; maj.h_max=0; poczatek=0; koniec=n; //koniec czyszczenia for(int i=0; i<n; ++i){ scanf("%lld %lld %lld %lld", &szyba[i].w_min, &szyba[i].w_max, &szyba[i].h_min, &szyba[i].h_max); if(szyba[i].w_min<maj.w_min)maj.w_min=szyba[i].w_min; if(szyba[i].w_max>maj.w_max)maj.w_max=szyba[i].w_max; if(szyba[i].h_min<maj.h_min)maj.h_min=szyba[i].h_min; if(szyba[i].h_max>maj.h_max)maj.h_max=szyba[i].h_max; } sort(szyba,szyba+n,por); koniec=za_malo_czasu_by_pisac_binary_searcha(maj.w_min,poczatek,koniec,1); poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.w_max,poczatek,koniec,2); koniec=za_malo_czasu_by_pisac_binary_searcha(maj.h_min,poczatek,koniec,3); poczatek=za_malo_czasu_by_pisac_binary_searcha(maj.h_max,poczatek,koniec,4); if(koniec<=poczatek){ printf("NIE\n"); continue; } printf("TAK\n"); } return 0; } |