题目:
给一个管子,有很多转弯处,问从管口的射线射进去最长能射到多远
题解:
根据黑书,可以证明的是这条光线一定经过了一个上顶点和下顶点
所以我们枚举每对上下顶点就可以了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-5
using namespace std;
bool dcmp(double x,double y)
{
if (fabs(x-y)>eps) return 1;
return 0;
}
struct point
{
double x,y;
point () {};
point (double _x,double _y)
{
x=_x,y=_y;
}
point operator + (const point &a)const
{
return point(x+a.x,y+a.y);
}
point operator - (const point &a) const
{
return point(x-a.x,y-a.y);
}
double operator * (const point &a)const
{
return x*a.y-a.x*y;
}
double dot (const point &a,const point &b)
{
return a.x*b.x+a.y*b.y;
}
bool operator < (const point &a)const
{
return x<a.x;
}
bool operator == (const point &a)const
{
return dcmp(x,a.x) && dcmp(y,a.y);
}
}up[105],down[105];
inline double Max(double a,double b)
{
return a>b?a:b;
}
double Multi(point a,point b,point c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool Across(point a,point b,point c,point d)
{
double tmp=Multi(c,b,a)*Multi(d,b,a);
if (tmp<0 || fabs(tmp)<eps) return 1;
return 0;
}
double getIntersect(point a,point b,point c,point d)
{
double A1=b.y-a.y,B1=a.x-b.x,C1=(b.x-a.x)*a.y-(b.y-a.y)*a.x;
double A2=d.y-c.y,B2=c.x-d.x,C2=(d.x-c.x)*c.y-(d.y-c.y)*c.x;
return (C2*B1-C1*B2)/(A1*B2-A2*B1);
}
int n,flag;
double ans;
int main()
{
while (scanf("%d",&n) && n)
{
for (int i=0;i<n;i++)
{
scanf("%lf%lf",&up[i].x,&up[i].y);
down[i].x=up[i].x;
down[i].y=up[i].y-1;
}
ans=up[0].x;
flag=0;
for (int i=0;i<n && !flag;i++)
for (int j=0;j<n && !flag;j++)
if (i!=j)
{
int k;
for (k=0;k<n;k++)
if (!Across(up[i],down[j],up[k],down[k])) break;
if (k==n) flag=1;
else if (k>i && k>j)
{
double tmp;
tmp=getIntersect(up[i],down[j],up[k-1],up[k]);
// printf("%.2f\n",tmp);
if (tmp>ans) ans=tmp;
tmp=getIntersect(up[i],down[j],down[k-1],down[k]);
// printf("%.2f\n",tmp);
if (tmp>ans) ans=tmp;
}
}
if (flag) puts("Through all the pipe.");
else printf("%.2f\n",ans);
}
return 0;
}
POJ 1039 Pipe | 线段相交的更多相关文章
-
[poj 1039]Pipes[线段相交求交点]
题意: 无反射不透明管子, 问从入口射入的所有光线最远能到达的横坐标. 贯穿也可. 思路: 枚举每一组经过 up [ i ] 和 down [ j ] 的直线, 计算最远点. 因为无法按照光线生成的方 ...
-
POJ 1039 Pipe【经典线段与直线相交】
链接: http://poj.org/problem?id=1039 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22013#probl ...
-
简单几何(直线与线段相交) POJ 1039 Pipe
题目传送门 题意:一根管道,有光源从入口发射,问光源最远到达的地方. 分析:黑书上的例题,解法是枚举任意的一个上顶点和一个下顶点(优化后),组成直线,如果直线与所有竖直线段有交点,则表示能穿过管道. ...
-
POJ 1039 Pipe(直线和线段相交判断,求交点)
Pipe Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8280 Accepted: 2483 Description ...
-
POJ - 1039 Pipe(计算几何)
http://poj.org/problem?id=1039 题意 有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从左边入 ...
-
poj 1066(枚举+线段相交)
Treasure Hunt Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 6328 Accepted: 2627 Des ...
-
poj 1039 Pipe (Geometry)
1039 -- Pipe 理解错题意一个晚上._(:з」∠)_ 题意很容易看懂,就是要求你求出从外面射进一根管子的射线,最远可以射到哪里. 正解的做法是,选择上点和下点各一个,然后对于每个折点位置竖直 ...
-
POJ 1039 Pipe 枚举线段相交
Pipe Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 9493 Accepted: 2877 Description ...
-
poj 1039 Pipe(叉乘。。。)
题目:http://poj.org/problem?id=1039 题意:有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从 ...
随机推荐
-
Python黑帽编程1.2 基于VS Code构建Python开发环境
Python黑帽编程1.2 基于VS Code构建Python开发环境 0.1 本系列教程说明 本系列教程,采用的大纲母本为<Understanding Network Hacks Atta ...
-
Ubuntu下面su初始密码设置
rcm@rcm:~$ sudo passwd 输入新的 UNIX 密码: 重新输入新的 UNIX 密码: passwd:已成功更新密码
-
让footer在底部(测试它人方法)
要求:网页布局中,页脚在底部.内容不够一页时,在底部.内容超过一页时,出现卷动条,页脚也在被挤到底部 1.测试的这个文章介绍的办法 链接: http://www.cnblogs.com/cheny ...
-
html浏览器兼容性 JavaScript语法
1. 在FireFox中能够使用与HTML节点对象ID属性值同样的JS变量名称,可是IE中不行. 解决的方法:在命名上区分HTML节点对象ID属性值和JS变量 2. IE不支持JS ...
-
Python 学习笔记8
在最想放弃的时候 想想美好的事情 想想明天. 今天继续看错误与异常. http://www.pythondoc.com/pythontutorial3/errors.html
-
linux命令dd
原文链接: http://blog.csdn.net/adaptiver/article/details/6672592 dd 使用dd这个linux命令可以创建一定大小文件. linux创建文件命令 ...
-
关于 Duplicate detection rules 自动 unpublish 的问题
最近发现自己建立的 Duplicate detection rules 在 publish 之后,会不定时地变成 unpublish 的状态,经过几次测试后,发现是每次将开发中版本更新到测试的 sit ...
-
ES6 语法学习(一)
1.let 和 const 关键字 let 与 var 的区别有: a.let 声明的变量只在当前的块级作用域内有效(块级作用域通俗的话就是被{}包裹起来的区域声明对象的{}例外). b.let 声明 ...
-
JSONObject基本内容(二)
参考内容:http://swiftlet.net/archives/category/json 十分感谢!!! 这部分的内容主要是讲述 javaBean转换为JSONObect时,如果有些属性不需要 ...
-
[java]String和Date、Timestamp之间的转换
一.String与Date(java.util.Date)互转 1.1 String -> Date Date date = DateFormat.parse(String str); St ...