/*开始的时候并查集写错了。就是有传递闭包的关系。不错的一个题。*/
#include <stdio.h>
#define eps 1e-8
double max(double a,double b)
{
if(b-a<-eps) return a;
else return b;
}
double min(double a,double b)
{
if(b-a<-eps) return b;
else return a;
}
struct point
{
double x,y;
};
struct LINE
{
point p1,p2;
}line[14];
int f[14];
double multi(point p0,point p1,point p2)
{
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
bool cross(LINE a,LINE b)
{
if(min(a.p1.x,a.p2.x)-max(b.p1.x,b.p2.x)<eps
&&min(a.p1.y,a.p2.y)-max(b.p1.y,b.p2.y)<eps
&&min(b.p1.x,b.p2.x)-max(a.p1.x,a.p2.x)<eps
&&min(b.p1.y,b.p2.y)-max(a.p1.y,a.p2.y)<eps
&&multi(a.p1,a.p2,b.p1)*multi(a.p1,a.p2,b.p2)<=eps
&&multi(b.p1,b.p2,a.p1)*multi(b.p1,b.p2,a.p2)<=eps)
return true;
else return false;
}
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
void unit(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return ;
else f[y]=x;
}
int main()
{
int n,r,t;
while(scanf("%d",&n)==1&&n)
{
for(int i=1; i<=n; i++)
f[i]=i;
for(int i=1; i<=n; i++)
scanf("%lf%lf%lf%lf",&line[i].p1.x,&line[i].p1.y,&line[i].p2.x,&line[i].p2.y);
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
{
if(cross(line[i],line[j]))
unit(i,j);
}
while(scanf("%d%d",&r,&t)==2)
{
if(r==0&&t==0) break;
if(find(r)==find(t))
printf("CONNECTED\n");
else printf("NOT CONNECTED\n");
}
}
return 0;
}
更多详细信息请查看
java教程网 http://www.itchm.com/forum-59-1.html
分享到:
相关推荐
In the game of Jack Straws, a number of plastic or wooden ``straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. Here, we are only concerned ...
poj 1127 Jack Straws.md
pre_o_1csdn63m9a1bs0e1rr51niuu33e.a
matlab建立计算力学课程的笔记和文件.zip
FT_Prog_v3.12.38.643--FTD USB 工作模式设定及eprom读写
matlab基于RRT和人工势场法混合算法的路径规划.zip
matlab基于matlab的两步定位软件定义接收机的开源GNSS直接位置估计插件模块.zip
office 2016三和一精简版
文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
麦肯锡咨询顾问必备宝典-时间管理.ppt
文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
麦肯锡顾问的黄金思考方法.pptx
91fdd461elb59a4ce8dfcfc46bc283a7.msi
ansys maxwell
5-5
xx广告促销计划流程实施手册.ppt
仿小米商城微信小程序源码+项目说明.zip
文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
文件操作、数据分析和网络编程等。Python社区提供了大量的第三方库,如NumPy、Pandas和Requests,极大地丰富了Python的应用领域,从数据科学到Web开发。Python库的丰富性是Python成为最受欢迎的编程语言之一的关键原因之一。这些库不仅为初学者提供了快速入门的途径,而且为经验丰富的开发者提供了强大的工具,以高效率、高质量地完成复杂任务。例如,Matplotlib和Seaborn库在数据可视化领域内非常受欢迎,它们提供了广泛的工具和技术,可以创建高度定制化的图表和图形,帮助数据科学家和分析师在数据探索和结果展示中更有效地传达信息。
麦肯锡xx客户满意服务.ppt