POJ-3304 Segments (判断是否存在一条直线交所以线段)

2024-01-08 14:08

本文主要是介绍POJ-3304 Segments (判断是否存在一条直线交所以线段),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题:

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input

Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1yxy2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output

For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10-8.

Sample Input
3
2
1.0 2.0 3.0 4.0
4.0 5.0 6.0 7.0
3
0.0 0.0 0.0 1.0
0.0 1.0 0.0 2.0
1.0 1.0 2.0 1.0
3
0.0 0.0 0.0 1.0
0.0 2.0 0.0 3.0
1.0 1.0 2.0 1.0
Sample Output
Yes!
Yes!
No!

题目大意:

给你n(n<=100)条线段,问你是否存在一条直线,使得这些线段到这条直线上的投影有一个公共点、

解题思路:

我们可以把题意转化一下。如果存在这么一个公共点,那么从这个公共点向所在直线引一条垂线,这条垂线就会穿过所有线段。那如果我们找到了经过所有线段的直线,然后做垂线就能得到我们要的的那条直线。

题目转化为是否存在一条直线交所有线段。

如果要找这么一条直线,那么我们考虑最极限的情况,即这条直线刚好经过两条线段的端点。注意到n只有100,我们可以暴力枚举,判断是否成立。

判断直线与线段是否相交的方法是:

只要判断这条直线向量与从一点到线段两点向量的叉积就行,叉积同号就说明不相交,异号说明相交。

#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<iostream>
#include<vector>
#include<map>using namespace std;
const int maxn = 105;
const double eps = 1e-8;struct Point{double x, y;Point(double x = 0.0, double y = 0.0):x(x),y(y){}
};
struct Line{Point a,b;
}l[maxn];Point operator - (Point A, Point B){return Point(A.x-B.x,A.y-B.y);}double Cross(Point A, Point B)
{return A.x*B.y-A.y*B.x;
}
double Dot(Point A,Point B) {return A.x*B.x+A.y*B.y;}
double Length(Point A) {return sqrt(Dot(A,A));}
int dcmp(double x) {if (fabs(x) < eps) return 0;return x < 0? -1: 1;} int isOK(Point A, Point B, Point C, Point D)
{Point v1 = B-A, v2 = C-A, v3 = D-A;double flag1 = Cross(v1,v2);double flag2 = Cross(v1,v3);if(flag1*flag2<=0.000000001) return 1;else return 0;
}
int n;int judge(Point a, Point b)
{if(dcmp(Length(a-b))==0)return 0;for(int i = 1; i <= n; i++){if(!isOK(a,b,l[i].a,l[i].b))return 0;}
//    cout <<"## "<< a.x<<" "<< a.y<<" "<<b.x<<" "<<b.y<<endl;return 1;
}int solve()
{for(int i = 1; i <= n; i++){for(int j = 1; j<= n; j++){if(judge(l[i].a,l[j].a)||judge(l[i].b,l[j].a)||judge(l[i].a,l[j].b)||judge(l[i].b,l[j].b))return 1;}}return 0;
}int main()
{int t;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%lf%lf%lf%lf", &l[i].a.x, &l[i].a.y, &l[i].b.x, &l[i].b.y);int flag = solve();if(flag||n==1)printf("Yes!\n");elseprintf("No!\n");}return 0;
}

 

 

 

这篇关于POJ-3304 Segments (判断是否存在一条直线交所以线段)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/583711

相关文章

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

查询Oracle数据库表是否被锁的实现方式

《查询Oracle数据库表是否被锁的实现方式》本文介绍了查询Oracle数据库表是否被锁的方法,包括查询锁表的会话、人员信息,根据object_id查询表名,以及根据会话ID查询和停止本地进程,同时,... 目录查询oracle数据库表是否被锁1、查询锁表的会话、人员等信息2、根据 object_id查询被

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for