#include #include #include #define N (200) struct rect_t { int x1, y1, x2, y2; bool adj[N]; int group; }; using namespace std; bool intersect(int ax1, int ax2, int bx1, int bx2) { if(ax1 == bx1 || ax2 == bx2) return true; if(ax1 == bx2 || ax2 == bx1) return true; if(bx1 < ax1 && ax1 < bx2) return true; if(ax1 < bx1 && bx1 < ax2) return true; return false; } void actual_main(fstream &in) { rect_t R[N]; int n; in >> n; for(int i = 0; i < n; i++) { in >> R[i].x1 >> R[i].y1; // lower-left in >> R[i].x2 >> R[i].y2; // upper-right for(int j = 0; j < i; j++) { bool flag = true; flag &= intersect(R[i].x1, R[i].x2, R[j].x1, R[j].x2); flag &= intersect(R[i].y1, R[i].y2, R[j].y1, R[j].y2); R[j].adj[i] = R[i].adj[j] = flag; } R[i].adj[i] = false; } for(int i = 0; i < n; i++) { R[i].group = -1; } int n_group = 0; for(int i = 0; i < n; i++) { if(R[i].group >= 0) { continue; } queue q; q.push(i); while(!q.empty()) { int top = q.front(); q.pop(); if(R[top].group >= 0) continue; R[top].group = n_group; for(int j = 0; j < n; j++) { if(R[j].adj[top] && R[j].group < 0) q.push(j); } } ++n_group; } cout << n_group << endl; } int main(void) { fstream fin("rect.txt"); int n; fin >> n; for(int i = 0; i < n; i++) actual_main(fin); return 0; }