HDu 1558(線分交差+並列調査セット)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1558
考え方:主に線分の交差を判断し、交差すれば合併し、sum値を修正すればよい.

 1 #include<iostream>

 2 #include<cstdio>

 3 #include<cstring>

 4 #include<algorithm>

 5 #include<cmath>

 6 using namespace std;

 7 #define MAXN 1111

 8 #define eps 1e-7

 9 int parent[MAXN];

10 int sum[MAXN];

11 int n;

12 struct Node{

13     double x1,y1,x2,y2;

14 }node[MAXN];

15 

16 void Initiate()

17 {

18     for(int i=1;i<=n;i++){

19         parent[i]=i;

20         sum[i]=1;

21     }

22 }

23 

24 int Find(int x)

25 {

26     if(x==parent[x])

27         return x;

28     parent[x]=Find(parent[x]);

29     return parent[x];

30 }

31 

32 void Union(int u,int v)

33 {

34     int r1=Find(u),r2=Find(v);

35     if(r1==r2)return ;

36     parent[r1]=r2;

37     sum[r2]+=sum[r1];

38 }

39 

40 double Multiply1(const Node &p,const Node &q)

41 {

42     return (p.x1-p.x2)*(q.y1-p.y1)-(p.y1-p.y2)*(q.x1-p.x1);

43 }

44 

45 double Multiply2(const Node &p,const Node &q)

46 {

47     return (p.x1-p.x2)*(q.y2-p.y1)-(p.y1-p.y2)*(q.x2-p.x1);

48 }

49 

50 bool Judge(const Node &p,const Node &q)

51 {

52     if(max(p.x1,p.x2)>=min(q.x1,q.x2)&&

53     max(q.x1,q.x2)>=min(p.x1,p.x2)&&

54     max(p.y1,p.y2)>=min(q.y1,q.y2)&&

55     max(q.y1,q.y2)>=min(p.y1,p.y2)&&

56     Multiply1(p,q)*Multiply2(p,q)<=eps&&

57     Multiply1(q,p)*Multiply2(q,p)<=eps)

58     return true;

59     else return false;

60 }

61 

62 

63 int main()

64 {

65     int _case,i,x,t=0;

66     char str[2];

67     scanf("%d",&_case);

68     while(_case--)

69     {

70         if(t++)puts("");

71         scanf("%d",&n);

72         Initiate();

73         i=1;

74         while(n--){

75             scanf("%s",str);

76             if(str[0]=='P'){

77                 scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);

78                 for(int j=1;j<i;j++){

79                     if(Judge(node[j],node[i])){

80                         Union(j,i);

81                     }

82                 }

83                 i++;

84             }else {

85                 scanf("%d",&x);

86                 x=Find(x);

87                 printf("%d
",sum[x]);

88             }

89         }

90     }

91     return 0;

92 }

View Code