现在的位置: 首页 > 综合 > 正文

HDU 1558 Segment set 并查集加计算几何

2018年01月20日 ⁄ 综合 ⁄ 共 2312字 ⁄ 字号 评论关闭

Segment set

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3474    Accepted Submission(s): 1295

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
1 2 2 2 5
//hdoj 1558 并查集加计算几何 
#include<iostream>
#include<stdio.h> 
using namespace std;

struct point{
	double x,y;
};

struct bian{	
	point a,b;
};

bian edge[1001];
int E;
int pre[1001],sum[1001];

int find(int x)
{
	if(x==pre[x])	return x;
		else pre[x]=find(pre[x]);
	return pre[x];
}

void merge(int a,int b)
{
	int x,y;
	x=find(a);
	y=find(b);
	if(x!=y)
	{
		pre[x]=y;
		sum[y]+=sum[x];		
	}
}

//计算几何部分 线段相交的内容参考算法导论P577 
double xmult(point a,point b,point c)//大于零代表a,b,c左转
{  
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);  
}  

bool OnSegment(point a,point b,point c)//a,b,c共线时有效 
{          
    return c.x>=min(a.x,b.x)&&c.x<=max(a.x,b.x)&&c.y>=min(a.y,b.y)&&c.y<=max(a.y,b.y);    
}  
  
bool cross(point a,point b,point c,point d){//判断ab 与cd是否相交   
    double d1,d2,d3,d4;  
    d1=xmult(c,d,a);  
    d2=xmult(c,d,b);  
    d3=xmult(a,b,c);  
    d4=xmult(a,b,d);  
    if(d1*d2<0&&d3*d4<0)  return 1;  
    else    if(d1==0&&OnSegment(c,d,a)) return 1;  
    else    if(d2==0&&OnSegment(c,d,b)) return 1;  
    else    if(d3==0&&OnSegment(a,b,c)) return 1;  
    else    if(d4==0&&OnSegment(a,b,d)) return 1;  
    return 0;  
}   

int main()
{
	int T,n,i,j,k;
	char str[3]; 
	
//	freopen("test.txt","r",stdin);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		E=0;
		
		for(i=1;i<=n;i++)
			pre[i]=i,sum[i]=1;
		for(i=1;i<=n;i++)
		{
			scanf("%s",str);
			if(str[0]=='P')
			{
				E++;
				scanf("%lf%lf%lf%lf",&edge[E].a.x,&edge[E].a.y,&edge[E].b.x,&edge[E].b.y);
				for(j=1;j<E;j++)
					if(find(E)!=find(j)&&cross(edge[E].a,edge[E].b,edge[j].a,edge[j].b))
						merge(E,j);
			}
			else if(str[0]=='Q')
			{
				scanf("%d",&k);
				printf("%d\n",sum[find(k)]);
			}
			
		}
		if(T!=0) printf("\n");
	}
	return 0;
}

抱歉!评论已关闭.