本文主要是介绍[ACM] hdu Jack Straws,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Jack Straws
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 5 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Input
When n=0,the input is terminated.
There will be no illegal input and there are no zero-length straws.
Output
Sample Input
7 1 6 3 3 4 6 4 9 4 5 6 7 1 4 3 5 3 5 5 5 5 2 6 3 5 4 7 2 1 4 1 6 3 3 6 7 2 3 1 3 0 02 0 2 0 0 0 0 0 1 1 1 2 2 1 2 0 00
Sample Output
CONNECTED NOT CONNECTED CONNECTED CONNECTED NOT CONNECTED CONNECTED CONNECTED CONNECTED CONNECTED
Author
Source
题目关键点是判断两线段是否相交和并查集的使用。两个线段可以直接相交也可以通过其它线段间接相交,题目中的意思是不管两个线段是直接还是间接相交,都输出CONNECTED ,否则输出 NOT CONNECTED。并查集的使用是把所有相交的线段放在同一个集合里面(包括直接相交和间接相交),查询的时候,如果两个线段在同一集合(有相同的根节点)就是相交的情况。
代码:
#include <iostream>
#include <algorithm>
using namespace std;struct point//构造点
{int x,y;
};
struct line//构造线段
{point a,b;
};double multi(point p1,point p2,point p0)//矩形面积
{return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}bool intersect(line u,line v)//判断两线段是否相交
{return( (max(u.a.x,u.b.x)>=min(v.a.x,v.b.x))&&(max(v.a.x,v.b.x)>=min(u.a.x,u.b.x))&&(max(u.a.y,u.b.y)>=min(v.a.y,v.b.y))&&(max(v.a.y,v.b.y)>=min(u.a.y,u.b.y))&&(multi(v.a,u.b,u.a)*multi(u.b,v.b,u.a)>=0)&&(multi(u.a,v.b,v.a)*multi(v.b,u.b,v.a)>=0));
}int parent[14];//父节点
int rank[14];//树高
int n;
line lin[14];//线段数void init(int n)//初始化集合,每条线段都是一个独立的集合,树高全部为0
{for(int i=1;i<=n;i++){parent[i]=i;rank[i]=0;}
}int find(int x)//找根节点
{return parent[x]==x?x:find(parent[x]);
}void unite(int x,int y)//把两个集合合并,树高(rank)小的向大的那边合并。
{x=find(x);y=find(y);if(x==y)return;if(rank[x]<rank[y])parent[x]=y;else{parent[y]=x;if(rank[x]==rank[y])rank[x]++;}}bool same(int x,int y)//判断两条线段是否有相同的根节点,也就是判断是否属于同一集合,同一集合的线段都相连(直接相连和间接相连)
{return find(x)==find(y);
}
int main()
{while(cin>>n&&n){for(int i=1;i<=n;i++){cin>>lin[i].a.x>>lin[i].a.y>>lin[i].b.x>>lin[i].b.y;}init(n);for(int i=1;i<=n;i++)//集合合并过程for(int j=i+1;j<=n;j++){if(intersect(lin[i],lin[j]))//如果第i条线段和第j条线段相交unite(i,j);}int l1,l2;while(cin>>l1>>l2&&l1&&l2){if(same(l1,l2))cout<<"CONNECTED"<<endl;elsecout<<"NOT CONNECTED"<<endl;}}return 0;
}
运行:
这篇关于[ACM] hdu Jack Straws的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!