Segment set
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2690 Accepted Submission(s): 1015
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.
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicGcq5SMtQDMwETLwUzQvw1cldWYtl2LcFGdhR2Lc52YuUHZl5SdkhmLtNWYvw1LcpDc0RHaiojIsJye.jpg)
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
1
2
2
2
5
Author LL
Source HDU 2006-12 Programming Contest
Recommend LL
題意:相交的直線算是一個集合,問低n條直線的集合有多少條直線
題解:直線相交模闆+并查集多開一個num初值為1的數組,将其合并可以了
#include<stdio.h>
#include<string.h>
#define eps 1e-6
int v[1005],num[1005];
struct segment{
double x1,y1,x2,y2;
}s[1005];
double MAX(double a,double b)
{
return a>b?a:b;
}
double MIN(double a,double b)
{
return a<b?a:b;
}
double multiply1(int a,int b)
{
return (s[a].x1-s[a].x2)*(s[b].y1-s[a].y1)-(s[a].y1-s[a].y2)*(s[b].x1-s[a].x1);
}
double multiply2(int a,int b)
{
return (s[a].x1-s[a].x2)*(s[b].y2-s[a].y1)-(s[a].y1-s[a].y2)*(s[b].x2-s[a].x1);
}
int judge(int a,int b)
{
if(MAX(s[a].x1,s[a].x2)>=MIN(s[b].x1,s[b].x2)&&
MAX(s[b].x1,s[b].x2)>=MIN(s[a].x1,s[a].x2)&&
MAX(s[a].y1,s[a].y2)>=MIN(s[b].y1,s[b].y2)&&
MAX(s[b].y1,s[b].y2)>=MIN(s[a].y1,s[a].y2)&&
multiply1(a,b)*multiply2(a,b)<=eps&&
multiply1(b,a)*multiply2(b,a)<=eps)
return 1;
else return 0;
}
int f(int x)
{
if(x==v[x]) return x;
return v[x]=f(v[x]);
}
int main()
{
int i,j,n,t,x,y,cou;
char ch;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<=n;i++) v[i]=i,num[i]=1;
for(cou=i=0;i<n;i++)
{
getchar();
scanf("%c",&ch);
if(ch=='P')
{
scanf("%lf%lf%lf%lf",&s[cou].x1,&s[cou].y1,&s[cou].x2,&s[cou].y2);
for(j=0;j<cou;j++)
{
if(judge(j,cou))
{
x=f(j),y=f(cou);
if(x==y) continue;
v[x]=y,num[y]+=num[x];
}
}
cou++;
}
else
{
scanf("%d",&x);
printf("%d\n",num[f(x-1)]);
}
}
if(t) printf("\n");
}
return 0;
}