1 /* 4775 */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int maxn = 10005;
 44 map<pii, int> id;
 45 map<pii, bool> visit;
 46 map<pii, int>::iterator iter;
 47 int X[maxn], Y[maxn];
 48 int sz[maxn], fa[maxn];
 49 int dir[4][2] = {
 50     -1,0, 1,0, 0,-1, 0,1
 51 };
 52 int n;
 53 
 54 int find(int x) {
 55     if (x == fa[x])
 56         return x;
 57     
 58     return fa[x] = find(fa[x]);
 59 }
 60 
 61 bool judge(int x, int y) {
 62     return x<=0 || y<=0;
 63 }
 64 
 65 void remove(int bx, int by, int uid) {
 66     queue<pii> Q;
 67     int x, y;
 68     pii p(bx, by), pp;
 69     
 70     visit.clr();
 71     Q.push(p);
 72     visit[p] = true;
 73     
 74     while (!Q.empty()) {
 75         p = Q.front();
 76         Q.pop();
 77         
 78         // remove from the id
 79         iter = id.find(p);
 80         fa[iter->sec] = iter->sec;
 81         sz[iter->sec] = 0;
 82         id.erase(iter);
 83         
 84         rep(j, 0, 4) {
 85             x = p.fir + dir[j][0];
 86             y = p.sec + dir[j][1];
 87             if (judge(x, y))
 88                 continue;
 89             
 90             pp.fir = x;
 91             pp.sec = y;
 92             if (visit[pp])
 93                 continue;
 94             
 95             iter = id.find(pp);
 96             if (iter == id.end())
 97                 continue;
 98             
 99             if ((iter->sec&1) ^ uid) {
100                 int f = find(iter->sec);
101                 ++sz[f];
102             } else {
103                 visit[pp] = true;
104                 Q.push(pp);
105             }
106         }
107     }
108 }
109 
110 void solve() {
111     rep(i, 0, n+1)
112         fa[i] = i;
113     memset(sz, 0, sizeof(sz));
114     id.clr();
115     
116     int vac, x, y;
117     int xx, yy;
118     pii p;
119     
120     rep(i, 1, n+1) {
121         p.fir = x = X[i];
122         p.sec = y = Y[i];
123         id[p] = i;
124         vac = 0;
125         rep(j, 0, 4) {
126             xx = x + dir[j][0];
127             yy = y + dir[j][1];
128             if (judge(xx, yy))
129                 continue;
130             
131             iter = id.find(mp(xx, yy));
132             if (iter == id.end()) {
133                 ++vac;
134             } else {
135                 int f = find(iter->sec);
136                 --sz[f];
137             }
138         }
139         sz[i] = vac;
140         rep(j, 0, 4) {
141             xx = x + dir[j][0];
142             yy = y + dir[j][1];
143             if (judge(xx, yy))
144                 continue;
145             
146             iter = id.find(mp(xx, yy));
147             if (iter == id.end())
148                 continue;
149             
150             if ((iter->sec & 1) ^ (i & 1)) {
151                 // delete enemy
152                 int fx = find(iter->sec);
153                 if (sz[fx] == 0) {
154                     remove(xx, yy, iter->sec&1);
155                 }
156                 
157             } else {
158                 // link self
159                 int fx = find(iter->sec);
160                 int fy = find(i);
161                 if (fx != fy) {
162                     fa[fx] = fy;
163                     sz[fy] += sz[fx];
164                 }
165             }
166         }
167         
168         int f = find(i);
169         if (sz[f] == 0) {
170             remove(x, y, i&1);
171         }
172     }
173     
174     int ansa, ansb;
175     
176     ansa = ansb = 0;
177     visit.clr();
178     per(i, 1, n+1) {
179         p.fir = X[i];
180         p.sec = Y[i];
181         iter = id.find(p);
182         if (iter==id.end() || visit[p])
183             continue;
184         
185         visit[p] = true;
186         if (iter->sec & 1)
187             ++ansa;
188         else
189             ++ansb;
190     }
191     
192     printf("%d %d\n", ansa, ansb);
193 }
194 
195 int main() {
196     ios::sync_with_stdio(false);
197     #ifndef ONLINE_JUDGE
198         freopen("data.in", "r", stdin);
199         freopen("data.out", "w", stdout);
200     #endif
201     
202     int t;
203     
204     scanf("%d", &t);
205     while (t--) {
206         scanf("%d", &n);
207         rep(i, 1, n+1)
208             scanf("%d %d", &X[i], &Y[i]);
209         solve();
210     }
211     
212     #ifndef ONLINE_JUDGE
213         printf("time = %d.\n", (int)clock());
214     #endif
215     
216     return 0;
217 }

 1 from random import randint, shuffle
 2 import shutil
 3 import string
 4 
 5 
 6 def GenDataIn():
 7     with open("data.in", "w") as fout:
 8         t = 10
 9         fout.write("%d\n" % t)
10         bound = 10**2
11         for tt in xrange(t):
12             n = randint(1000, 5000)
13             fout.write("%d\n" % n)
14             d = dict()
15             for i in xrange(n):
16                 while True:
17                     x = randint(1, bound)
18                     y = randint(1, bound)
19                     tpl = (x, y)
20                     if tpl not in d:
21                         d[tpl] = True
22                         break
23                 fout.write("%d %d\n" % (x, y))
24                 
25                 
26 def MovDataIn():
27     desFileName = "F:\eclipse_prj\workspace\hdoj\data.in"
28     shutil.copyfile("data.in", desFileName)
29 
30     
31 if __name__ == "__main__":
32     GenDataIn()
33     MovDataIn()