2010年02月13日星期六.sgu174
sgu174:并查集+二叉搜索树
说说题意吧。就是每次给出两个点，这两个点代表一条线段，如果这一条线段能和已经存在的线
段构成一个封闭多边形，那么就输出这是第几条线段。
很自然的能想到并查集，所差的就是为每一个点赋予一个唯一的编号。
如果线性的查找已经处理过的点，那么就每次查询的复杂度就是O(n).
而有n个这样的查询。当n如此大的时候，n^2的算法显然会超时。
我们需要提高每次查询的复杂度。
其实很容易就能想到二叉搜索树。不想写的话可以直接使用stl中的map,map是红黑树的实现，如
果不怕常数复杂度的话，这是一个很好的想法。
还有就是并查集，并查集需要加上路径压缩，不然很容易超时。
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.cppblog.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