Segments
Time Limit: 1000MS |
|
Memory Limit: 65536K |
Total Submissions: 3703 |
|
Accepted: 1026 |
Description
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 x1y1x2y2 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!
Source
这个题题意是:
求是否存在一条直线,使所有线段到这条直线的投影至少有一个交点
这个题目可以转化为是否有一条直线可以与所有的线段相交
简单证明一下:
如果存在一条直线可以满足题意,那么必然这条直线的垂线就一定可以与点集中任意两点连起来的那个线段相交,而且我们可以通过旋转这条直线让他和某一条线段重合
于是解题思路就变成了:
二重循环枚举端点,并且用这两个端点构成一条直线,并判断这条直线是不是可以与所有的线段相交
我的代码:
代码很快就敲出来了,不过一直得不到正确答案,调试了很久才发现我数组的下标全部是从1开始的,所以判断直线和线段相交的时候要写成if(k==n+1)先开始写成k==n了。。。
Source Code
Problem: 3304
|
|
User: bingshen
|
Memory: 200K |
|
Time: 32MS |
Language: C++ |
|
Result: Accepted
|
-
Source Code
#include<stdio.h>
#include<math.h>
#define eps 1e-8
struct point
{
double x;
double y;
};
struct line
{
point a;
point b;
};
point p[205];
line l[105];
double dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double cross(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool work(int n)
{
int i,j,k;
for(i=1;i<=2*n;i++)
{
for(j=i+1;j<=2*n;j++)
{
if(dis(p[i],p[j])<=eps)
continue;
for(k=1;k<=n;k++)
if(cross(l[k].a,p[i],p[j])*cross(l[k].b,p[i],p[j])>0)
break;
if(k==n+1)
return true;
}
}
return false;
}
int main()
{
int i,n,t;
double x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
p[2*i-1].x=x;
p[2*i-1].y=y;
scanf("%lf%lf",&x,&y);
p[2*i].x=x;
p[2*i].y=y;
l[i].a=p[2*i-1];
l[i].b=p[2*i];
}
if(work(n))
printf("Yes!/n");
else
printf("No!/n");
}
return 0;
}
没有天分,只有勤奋~~
分享到:
相关推荐
北大POJ初级-计算几何学 解题报告+AC代码
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1.13 矢量运算求几何模板 35 ...
poj 2653 计算几何算法初步模板,判断两直线是否相交。
计算几何半平面交,poj2451 一题是模版题,这里的代码可以作为模版使用,速度比较快
计算几何基本知识以及做题时需要注意的地方 ppt
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 //表示举例 非主流算法: 1.送分题 2.构造 3.高精度 4.几何 5.排序 6.日期/...
解决poj1005买地问题,涉及几何计算
poj 2121 好用的计算几何模板 好用相当好用的,用用看看
6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya 定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、回溯、遍历 3、历法 4、 枚举 5、 数据结构的典型算法 6、 动态规划
解法或类型: 计算几何 作者:杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h ...
解法或类型: 计算几何 作者:杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h ...
解法或类型: 计算几何 作者:杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h ...
解法或类型: 计算几何 作者:杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h ...
解法或类型: 计算几何 作者:杨清玄 Fence Time Limit:1S Memory Limit:1000K Total Submit:103 Accepted:26 Description There is an area bounded by a fence on some flat field. The fence has the height h ...
算法训练方案,一步步掌握个各种算法。。一.基本算法: 二.图算法:三.数据结构.四.简单搜索五.动态规划六.数学七.计算几何学.中级:
3.6 与平面和空间打交道的计算几何 3.6.1 计算几何基础 3.6.2 极限情况 3.6.3 平面扫描 3.6.4 凸包 3.6.5 数值积分 3.7 一起来挑战GCJ的题目(2) 3.7.1 Numbers 3.7.2 No Cheating 3.7.3 Stock Charts 3.7.4 ...
leetcode 和 oj Algorithm and Data structure ACM题解和一些算法的实现 ...涉及搜索,动态规划,数学,图论,计算几何,数据结构等。 总结的经典算法的模板 智力题 联系作者 E-mail: acm_tach at 163.com
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...