題意很簡單，給出一些線段，組成一些數(shù)字，保持數(shù)字連接點的聯(lián)通關(guān)系不變（就說是圖的邏輯結(jié)構(gòu)不變吧），并且保證沒有相交。要求識別數(shù)字。
首先這題，涉及到并查集的運用。開始犯了個很糊涂的錯誤，本題新加上一條線段可能造成2種情況
1、A - C，新加線為C，就是把C連接到某個樹枝上
2、A-C-B，這種情況考慮漏了，就是通過C這個線把倆個不連通的集合給打通了
具體代碼應(yīng)該是這樣
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;
這個就是只考慮了第一種情況。
關(guān)于數(shù)字識別的問題就好辦多了，主要根據(jù)部分相交和點相交的數(shù)目以及聯(lián)通集中線段的數(shù)目來判斷數(shù)字（5和2還要根據(jù)叉積再來弄下），這題受益最深的就是并查集那里，容易犯的錯誤。
代碼如下：
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 }