这个主要是线段相交的处理，完全按照算法导论写一下几何就好了。并查集不想再说了。
叉积是好东西，同学们必须学会。
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<iomanip>
5 using namespace std;
6 const int maxnum=1000+1;
7 #define rep(i,n,m) for(int i=(n);i<=(m);++i)
8 #define re1(i,n) rep(i,1,n)
9 struct point{
10 double x,y;
11 point(){
12
13 }
14 point(double x,double y):x(x),y(y){
15
16 }
17 friend ostream& operator<<(ostream &out,point a){
18 out<<'('<<a.x<<','<<a.y<<')';
19 return out;
20 }
21 };
22 struct seg{
23 double x,y;
24 point from,to;
25 seg(){
26
27 }
28 seg(point a,point b):from(a),to(b){
29 double x1=a.x,x2=b.x;
30 double y1=a.y,y2=b.y;
31 x=x2-x1;
32 y=y2-y1;
33 }
34 };
35 double cross(seg a,seg b){
36 double x1=a.x,x2=b.x;
37 double y1=a.y,y2=b.y;
38 return x1*y2-y1*x2;
39 }
40 double cross(point p0,point p1,point p2){
41 return cross(seg(p0,p1),seg(p0,p2));
42 }
43 bool between(double a,double b,double x){
44 return x>=a && x<=b;
45 }
46 bool on_seg(point p1,point p2,point p0){
47 double x1=p1.x,x2=p2.x;
48 double y1=p1.y,y2=p2.y;
49 return between(min(x1,x2),max(x1,x2),p0.x) && between(min(y1,y2),max(y1,y2),p0.y);
50 }
51 bool intersect(point p1,point p2,point p3,point p4){
52 int d1=cross(p3,p4,p1);
53 int d2=cross(p3,p4,p2);
54 int d3=cross(p1,p2,p3);
55 int d4=cross(p1,p2,p4);
56 if(((d1>0 && d2<0)||(d1<0 && d2>0)) &&((d3>0 && d4<0) ||(d3<0 && d4>0)))
57 return true;
58 else if(d1==0 && on_seg(p3,p4,p1))
59 return true;
60 else if(d2==0 && on_seg(p3,p4,p2))
61 return true;
62 else if(d3==0 && on_seg(p1,p2,p3))
63 return true;
64 else if(d4==0 && on_seg(p1,p2,p4))
65 return true;
66 else
67 return false;
68
69 }
70 struct seg segs[maxnum];
71 int G[maxnum];
72 int num[maxnum];
73 int find(int x){
74 if(G[x]!=x)
75 G[x]=find(G[x]);
76 return G[x];
77 }
78 void u3n(int a,int b){
79 int x=find(a);
80 int y=find(b);
81 if(x==y)
82 return;
83 G[x]=y;
84 num[y]+=num[x];
85 }
86 void showline(int n,int m){
87 rep(i,n,m){
88 cout<<setw(6)<<i;
89 }
90 cout<<endl<<endl;
91 }
92 template<class T>
93 void show(T *a,int n,int m){
94 rep(i,n,m){
95 cout<<setw(6)<<a[i];
96 }
97 cout<<endl;
98 }
99 int main(){
100 int tcase;
101 scanf("%d",&tcase);
102 while(tcase--){
103 int m,n=0;
104 scanf("%d",&m);
105 char cmd[2];
106 re1(u,m){
107 G[u]=u;
108 num[u]=1;
109 }
110 re1(u,m){
111 scanf("%s",cmd);
112 if(cmd[0]=='P'){
113 double x1,y1,x2,y2;
114 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
115 segs[++n]=seg(point(x1,y1),point(x2,y2));
116 // cout<<segs[n].from<<' '<<segs[n].to<<endl;
117 re1(i,n-1){
118 if(intersect(segs[i].from,segs[i].to,segs[n].from,segs[n].to))
119 u3n(i,n);
120 }
121 }else{
122 int id;
123 scanf("%d",&id);
124 printf("%d\n",num[find(id)]);
125 }
126 }
127 //showline(1,6);
128 //show(G,1,6);
129 //show(num,1,6);
130 if(tcase)
131 printf("\n");
132 }
133 }
posted on 2012-12-10 21:31
Gin 阅读(407)
评论(0) 编辑 收藏 引用 所属分类:
Data Structure