5.1.3 Segment set

Segment set

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 120 Accepted Submission(s): 54

Problem Description

A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.

Input

In the first line there is an integer t - the number of test case. For each test case in first line there is an integer n (n<=1000) - the number of commands.

There are two different commands described in different format shown below:

P x1 y1 x2 y2 - paint a segment whose coordinates of the two endpoints are (x1,y1),(x2,y2).
Q k - query the size of the segment set which contains the k-th segment.

k is between 1 and the number of segments in the moment. There is no segment in the plane at first, so the first command is always a P-command.

Output

For each Q-command, output the answer. There is a blank line between test cases.

Sample Input

1
10
P 1.00 1.00 4.00 2.00
P 1.00 -2.00 8.00 4.00
Q 1
P 2.00 3.00 3.00 1.00
Q 1
Q 3
P 1.00 4.00 8.00 2.00
Q 2
P 3.00 3.00 6.00 -2.00
Q 5

Sample Output

Author

思路：就是判断当前线段与以前的线段是否相交且是否为同一集合，并查集很简单，就是计算几何我还不懂，网上找了个写的不错的贴出来（他考虑到了浮点误差！！）

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const double eps = 1e-12;
 7 const int size = 1000;
 8 
 9 struct point
10 {
11     double x, y;
12 };
13 
14 struct seg
15 {
16     point a, b;
17 } S[size + 20];
18 
19 double multi (  point p1, point p2,point p0)
20 {
21     return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
22 }
23 
24 bool isIntersected(point s1, point e1, point s2, point e2)
25 {
26     if(
27         (max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
28         (max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
29         (max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
30         (max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
31         (multi(s2, e1, s1) * multi(e1, e2, s1) >= -eps) &&
32         (multi(s1, e2, s2) * multi(e2, e1, s2) >= -eps)
33     )  return true;
34 
35     return false;
36 }
37 
38 int father[size + 10], n, rank[size + 10];
39 
40 
41 int Find_Set(int x)
42 {
43     if (x != father[x])
44     {
45         father[x] = Find_Set(father[x]);
46     }
47     return father[x];
48 }
49 
50 void Union(int x, int y)
51 {
52     x = Find_Set(x);
53     y = Find_Set(y);
54     if (x != y)
55     {
56         father[x] = y;
57     }
58 }
59 
60 int main()
61 {
62     int  t;
63     char ST[2];
64     scanf("%d", &t);
65     int tt = t;
66     while (t --)
67     {
68         if (t != tt - 1)printf("\n");
69         scanf("%d", &n);
70         int j = 0;
71         for (int i = 0; i < n; i ++)
72         {
73             scanf("%s", ST);
74             if (ST[0] == 'P')
75             {
76                 scanf("%lf%lf%lf%lf", &S[j].a.x, &S[j].a.y, &S[j].b.x, &S[j].b.y);
77                 father[j] = j;
78                 for (int k = 0; k < j; k ++)
79                 {
80                     if (isIntersected(S[j].a, S[j].b, S[k].a, S[k].b))
81                     {
82                         Union (j, k);
83                     }
84                 }
85                 j ++;
86             }
87             else if (ST[0] == 'Q')
88             {
89                 int s, sum = 0;
90                 scanf("%d", &s);
91                 for (int k = 0; k < j; k ++)
92                     if (Find_Set(s - 1) == Find_Set(k))sum ++;
93                 printf("%d\n", sum);
94             }
95         }
96 
97     }
98     return 0;
99 }