題意很簡單，給出一些線段，組成一些數字，保持數字連接點的聯通關系不變（就說是圖的邏輯結構不變吧），并且保證沒有相交。要求識別數字。
首先這題，涉及到并查集的運用。開始犯了個很糊涂的錯誤，本題新加上一條線段可能造成2種情況
1、A - C，新加線為C，就是把C連接到某個樹枝上
2、A-C-B，這種情況考慮漏了，就是通過C這個線把倆個不連通的集合給打通了
具體代碼應該是這樣
for(int j=0;j<now;j++)
if(find(now)!=find(j)&&cross(now,j))
set[find(now)]=find(j);
開始糊涂蛋的寫成了
for(int j=0;j<now;j++)
if(cross(now,j))
set[now]=find(j),break;
這個就是只考慮了第一種情況。
關于數字識別的問題就好辦多了，主要根據部分相交和點相交的數目以及聯通集中線段的數目來判斷數字（5和2還要根據叉積再來弄下），這題受益最深的就是并查集那里，容易犯的錯誤。
代碼如下：
1 Source Code
2
3 Problem: 3943 User: yzhw
4 Memory: 656K Time: 188MS
5 Language: G++ Result: Accepted
6 Source Code
7 # include <cstdio>
8 # include <vector>
9 # include <cstring>
10 # include <map>
11 using namespace std;
12 # define N 1005
13 # define min(a,b) ((a)<(b)?(a):(b))
14 # define max(a,b) ((a)>(b)?(a):(b))
15 struct line
16 {
17 int x1,y1,x2,y2;
18 }l[N];
19 bool in(int x,int y,const line &pos)
20 {
21 if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
22 y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
23 (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
24 return true;
25 else return false;
26 }
27 int cross(const line &a,const line &b)
28 {
29 if(a.x1==b.x1&&a.y1==b.y1||
30 a.x2==b.x1&&a.y2==b.y1||
31 a.x1==b.x2&&a.y1==b.y2||
32 a.x2==b.x2&&a.y2==b.y2) return 1;
33 else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
34 else return 0;
35 }
36 int cross(int x1,int y1,int x2,int y2)
37 {
38 return x1*y2-x2*y1;
39 }
40 struct node
41 {
42 vector<line> data;
43 int type() const
44 {
45 int num[3]={0,0,0};
46 for(int i=0;i<data.size();i++)
47 for(int j=i+1;j<data.size();j++)
48 num[cross(data[i],data[j])]++;
49 if(num[1]==4&&num[2]==0)
50 {
51 if(data.size()==4) return 0;
52 else
53 {
54 int target=-1,x1,y1,x2,y2;
55 for(int i=0;i<data.size();i++)
56 {
57 bool flag=true;
58 for(int j=0;j<data.size()&&flag;j++)
59 if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
60 flag=false;
61 if(flag)
62 {
63 target=i;
64 x1=data[i].x2,y1=data[i].y2;
65 x2=data[i].x1,y2=data[i].y1;
66 break;
67 }
68 flag=true;
69 for(int j=0;j<data.size()&&flag;j++)
70 if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
71 flag=false;
72 if(flag)
73 {
74 target=i;
75 x1=data[i].x1,y1=data[i].y1;
76 x2=data[i].x2,y2=data[i].y2;
77 break;
78 }
79 }
80 for(int i=0;i<data.size();i++)
81 if(i!=target)
82 {
83 if(data[i].x1==x1&&data[i].y1==y1)
84 return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
85 else if(data[i].x2==x1&&data[i].y2==y1)
86 return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
87 }
88 }
89 printf("wa!\n");
90 while(true);
91 }
92 else if(num[1]==0&&num[2]==0)
93 return 1;
94 else if(num[1]==4&&num[2]==0)
95 return 2;
96 else if(num[1]==2&&num[2]==1)
97 return 3;
98 else if(num[1]==1&&num[2]==1)
99 return 4;
100 else if(num[1]==4&&num[2]==1)
101 return 6;
102 else if(num[1]==2&&num[2]==0)
103 return 7;
104 else if(num[1]==4&&num[2]==2)
105 return 8;
106 else if(num[1]==3&&num[2]==1)
107 return 9;
108 }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114 if(set[pos]==pos) return pos;
115 else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119 while(scanf("%d",&n)!=EOF&&n)
120 {
121 data.clear();
122 memset(ans,0,sizeof(ans));
123 for(int i=0;i<n;i++)
124 {
125 set[i]=i;
126 scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127 for(int j=0;j<i;j++)
128 if(cross(l[i],l[j])&&find(i)!=find(j))
129 set[find(i)]=find(j);
130 }
131 for(int i=0;i<n;i++)
132 data[find(i)].data.push_back(l[i]);
133 for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134 ans[i->second.type()]++;
135 printf("%d",ans[0]);
136 for(int i=1;i<10;i++)
137 printf(" %d",ans[i]);
138 printf("\n");
139 }
140 return 0;
141 }