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

相关文章

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

shell脚本快速检查192.168.1网段ip是否在用的方法

《shell脚本快速检查192.168.1网段ip是否在用的方法》该Shell脚本通过并发ping命令检查192.168.1网段中哪些IP地址正在使用,脚本定义了网络段、超时时间和并行扫描数量,并使用... 目录脚本:检查 192.168.1 网段 IP 是否在用脚本说明使用方法示例输出优化建议总结检查 1

python 字典d[k]中key不存在的解决方案

《python字典d[k]中key不存在的解决方案》本文主要介绍了在Python中处理字典键不存在时获取默认值的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录defaultdict:处理找不到的键的一个选择特殊方法__missing__有时候为了方便起见,

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11