#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef pair<int,int> PII; int x1[20005]; int x2[20005]; int y2[20005]; int x21[20005]; int x22[20005]; int y21[20005]; int y22[20005]; int wysokosc[20005]; int szerokosc[20005]; int odw[20005]; int coscos[20005]; vector<PII>v,v2; int main(){ ios_base::sync_with_stdio(0); int t; cin >> t; for(int k=0; k<t; k++){ int n,w; cin >> n >> w; for(int i=0; i<n; i++){ int a,b,c,d; cin >> x1[i] >> coscos[i] >> x2[i] >> y2[i]; } for(int i=0; i<n; i++){ if(x1[i]<x2[i]) szerokosc[i]=x1[i]-x2[i]; else szerokosc[i]=x2[i]-x1[i]; if(coscos[i]>=y2[i]) wysokosc[i]=coscos[i]-y2[i]; else wysokosc[i]=y2[i]-coscos[i]; } for(int i=0; i<n; i++){ if(x1[i]>=x2[i]) v.push_back(PII(x1[i], i)); else v.push_back(PII(x2[i],i)); } sort(v.begin(), v.end()); for(int i=0; i<n; i++){ cin >> x21[i] >> y21[i] >> x22[i] >> y22[i]; } for(int i=0; i<n; i++){ if(x21[i] < x22[i]) v2.push_back(PII(x21[i],i)); else v.push_back(PII(x22[i],i)); } sort(v.begin(),v.end()); sort(v2.begin(),v2.end()); bool prawda=false; for(int i=0; i<n; i++){ int a=v2[i].second; odw[v2[i].second]=1; for(int j=i-1; j>=0; j--){ if(odw[v[j].second]==1) continue; if(wysokosc[v2[i].second]+wysokosc[v[j].second]<w) continue; else{ prawda=true; break; } } if(prawda==true) continue; for(int j=i-1; j>=0; j--){ int b=min(x21[v2[i].second], x22[v2[i].second]); int c=max(x22[v2[j].second], x22[v2[j].second]); if(b>=c) continue; int d=max(y21[v2[i].second], y22[v2[i].second]); int e=max(y21[v2[j].second], y22[v2[j].second]); int f=min(y21[v2[i].second], y22[v2[i].second]); int g=min(y21[v2[j].second], y22[v2[j].second]); if(d>=e){ if(w-e<wysokosc[v2[i].second]) { prawda=true; break; } } else{ if(f<=g){ if(g<wysokosc[v2[i].second]){ prawda=true; break; } } } if(wysokosc[v2[i].second]+wysokosc[v2[j].second]<=w) continue; else prawda=true; } } if(prawda==false) cout << "TAK" << endl; else cout << "NIE" << endl; } 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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | #include <iostream> #include <algorithm> #include <vector> using namespace std; typedef pair<int,int> PII; int x1[20005]; int x2[20005]; int y2[20005]; int x21[20005]; int x22[20005]; int y21[20005]; int y22[20005]; int wysokosc[20005]; int szerokosc[20005]; int odw[20005]; int coscos[20005]; vector<PII>v,v2; int main(){ ios_base::sync_with_stdio(0); int t; cin >> t; for(int k=0; k<t; k++){ int n,w; cin >> n >> w; for(int i=0; i<n; i++){ int a,b,c,d; cin >> x1[i] >> coscos[i] >> x2[i] >> y2[i]; } for(int i=0; i<n; i++){ if(x1[i]<x2[i]) szerokosc[i]=x1[i]-x2[i]; else szerokosc[i]=x2[i]-x1[i]; if(coscos[i]>=y2[i]) wysokosc[i]=coscos[i]-y2[i]; else wysokosc[i]=y2[i]-coscos[i]; } for(int i=0; i<n; i++){ if(x1[i]>=x2[i]) v.push_back(PII(x1[i], i)); else v.push_back(PII(x2[i],i)); } sort(v.begin(), v.end()); for(int i=0; i<n; i++){ cin >> x21[i] >> y21[i] >> x22[i] >> y22[i]; } for(int i=0; i<n; i++){ if(x21[i] < x22[i]) v2.push_back(PII(x21[i],i)); else v.push_back(PII(x22[i],i)); } sort(v.begin(),v.end()); sort(v2.begin(),v2.end()); bool prawda=false; for(int i=0; i<n; i++){ int a=v2[i].second; odw[v2[i].second]=1; for(int j=i-1; j>=0; j--){ if(odw[v[j].second]==1) continue; if(wysokosc[v2[i].second]+wysokosc[v[j].second]<w) continue; else{ prawda=true; break; } } if(prawda==true) continue; for(int j=i-1; j>=0; j--){ int b=min(x21[v2[i].second], x22[v2[i].second]); int c=max(x22[v2[j].second], x22[v2[j].second]); if(b>=c) continue; int d=max(y21[v2[i].second], y22[v2[i].second]); int e=max(y21[v2[j].second], y22[v2[j].second]); int f=min(y21[v2[i].second], y22[v2[i].second]); int g=min(y21[v2[j].second], y22[v2[j].second]); if(d>=e){ if(w-e<wysokosc[v2[i].second]) { prawda=true; break; } } else{ if(f<=g){ if(g<wysokosc[v2[i].second]){ prawda=true; break; } } } if(wysokosc[v2[i].second]+wysokosc[v2[j].second]<=w) continue; else prawda=true; } } if(prawda==false) cout << "TAK" << endl; else cout << "NIE" << endl; } return 0; } |