2010年02月13日星期六.sgu174
sgu174:并查集+二叉搜索樹
說(shuō)說(shuō)題意吧。就是每次給出兩個(gè)點(diǎn)，這兩個(gè)點(diǎn)代表一條線段，如果這一條線段能和已經(jīng)存在的線
段構(gòu)成一個(gè)封閉多邊形，那么就輸出這是第幾條線段。
很自然的能想到并查集，所差的就是為每一個(gè)點(diǎn)賦予一個(gè)唯一的編號(hào)。
如果線性的查找已經(jīng)處理過(guò)的點(diǎn)，那么就每次查詢的復(fù)雜度就是O(n).
而有n個(gè)這樣的查詢。當(dāng)n如此大的時(shí)候，n^2的算法顯然會(huì)超時(shí)。
我們需要提高每次查詢的復(fù)雜度。
其實(shí)很容易就能想到二叉搜索樹。不想寫的話可以直接使用stl中的map,map是紅黑樹的實(shí)現(xiàn)，如
果不怕常數(shù)復(fù)雜度的話，這是一個(gè)很好的想法。
還有就是并查集，并查集需要加上路徑壓縮，不然很容易超時(shí)。
1
2 const int N = 400010;
3 struct point_t {
4 int x,y;
5 point_t(){}
6 point_t(int a,int b){x = a,y = b;}
7 }a,b;一bool operator < (point_t a,point_t b)
8 {
9 if (a.x != b.x) {
10 return a.x < b.x;
11 }
12 return a.y < b.y;
13 }
14 map<point_t,int> g;
15 int n, p[N],rank[N];
16
17 int findset(int x)
18 {
19 if (p[x] != x) {
20 p[x] = findset(p[x]);
21 }
22 return p[x];
23 }
24 //http://www.shnenglu.com/schindlerlee
25 bool unionset(int x,int y)
26 {
27 x = findset(x);
28 y = findset(y);
29 if (x == y) { return true; }
30 if (rank[x] > rank[y]) {
31 p[y] = x;
32 } else if (rank[x] < rank[y]) {
33 p[x] = y;
34 } else if (rank[x] == rank[y]) {
35 p[x] = y;
36 rank[y]++;
37 }
38 return false;
39 }
40
41 int main()
42 {
43 int i,ia,ib;
44 scanf("%d",&n);
45 for (i = 0;i < N;i++) { p[i] = i; }
46 for (i = 1;i <= n;i++) {
47 scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
48 if ((ia = g[a]) == 0) { ia = g[a] = i << 1; } //from 1
49 if ((ib = g[b]) == 0) { ib = g[b] = (i << 1) + 1; }
50 if (unionset(ia,ib)) {
51 printf("%d\n",i);
52 break;
53 }
54 }
55 if (i > n) {
56 printf("0\n");
57 }
58 return 0;
59 }
60