POJ 1039 Pipe | 线段相交

时间:2022-06-24 12:39:06

题目:

给一个管子,有很多转弯处,问从管口的射线射进去最长能射到多远


题解:

根据黑书,可以证明的是这条光线一定经过了一个上顶点和下顶点

所以我们枚举每对上下顶点就可以了

#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 | 线段相交的更多相关文章

  1. &lbrack;poj 1039&rsqb;Pipes&lbrack;线段相交求交点&rsqb;

    题意: 无反射不透明管子, 问从入口射入的所有光线最远能到达的横坐标. 贯穿也可. 思路: 枚举每一组经过 up [ i ] 和 down [ j ] 的直线, 计算最远点. 因为无法按照光线生成的方 ...

  2. POJ 1039 Pipe【经典线段与直线相交】

    链接: http://poj.org/problem?id=1039 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22013#probl ...

  3. 简单几何&lpar;直线与线段相交&rpar; POJ 1039 Pipe

    题目传送门 题意:一根管道,有光源从入口发射,问光源最远到达的地方. 分析:黑书上的例题,解法是枚举任意的一个上顶点和一个下顶点(优化后),组成直线,如果直线与所有竖直线段有交点,则表示能穿过管道. ...

  4. POJ 1039 Pipe(直线和线段相交判断,求交点)

    Pipe Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 8280   Accepted: 2483 Description ...

  5. POJ - 1039 Pipe(计算几何)

    http://poj.org/problem?id=1039 题意 有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从左边入 ...

  6. poj 1066&lpar;枚举&plus;线段相交&rpar;

    Treasure Hunt Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 6328   Accepted: 2627 Des ...

  7. poj 1039 Pipe &lpar;Geometry&rpar;

    1039 -- Pipe 理解错题意一个晚上._(:з」∠)_ 题意很容易看懂,就是要求你求出从外面射进一根管子的射线,最远可以射到哪里. 正解的做法是,选择上点和下点各一个,然后对于每个折点位置竖直 ...

  8. POJ 1039 Pipe 枚举线段相交

    Pipe Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 9493   Accepted: 2877 Description ...

  9. poj 1039 Pipe(叉乘。。。)

    题目:http://poj.org/problem?id=1039 题意:有一宽度为1的折线管道,上面顶点为(xi,yi),所对应的下面顶点为(xi,yi-1),假设管道都是不透明的,不反射的,光线从 ...

随机推荐

  1. Python黑帽编程1&period;2 基于VS Code构建Python开发环境

    Python黑帽编程1.2  基于VS Code构建Python开发环境 0.1  本系列教程说明 本系列教程,采用的大纲母本为<Understanding Network Hacks Atta ...

  2. Ubuntu下面su初始密码设置

    rcm@rcm:~$ sudo passwd 输入新的 UNIX 密码: 重新输入新的 UNIX 密码: passwd:已成功更新密码

  3. 让footer在底部&lpar;测试它人方法&rpar;

    要求:网页布局中,页脚在底部.内容不够一页时,在底部.内容超过一页时,出现卷动条,页脚也在被挤到底部 1.测试的这个文章介绍的办法   链接: http://www.cnblogs.com/cheny ...

  4. html浏览器兼容性 JavaScript语法

    1.      在FireFox中能够使用与HTML节点对象ID属性值同样的JS变量名称,可是IE中不行. 解决的方法:在命名上区分HTML节点对象ID属性值和JS变量 2.      IE不支持JS ...

  5. Python 学习笔记8

    在最想放弃的时候 想想美好的事情 想想明天. 今天继续看错误与异常. http://www.pythondoc.com/pythontutorial3/errors.html

  6. linux命令dd

    原文链接: http://blog.csdn.net/adaptiver/article/details/6672592 dd 使用dd这个linux命令可以创建一定大小文件. linux创建文件命令 ...

  7. 关于 Duplicate detection rules 自动 unpublish 的问题

    最近发现自己建立的 Duplicate detection rules 在 publish 之后,会不定时地变成 unpublish 的状态,经过几次测试后,发现是每次将开发中版本更新到测试的 sit ...

  8. ES6 语法学习&lpar;一&rpar;

    1.let 和 const 关键字 let 与 var 的区别有: a.let 声明的变量只在当前的块级作用域内有效(块级作用域通俗的话就是被{}包裹起来的区域声明对象的{}例外). b.let 声明 ...

  9. JSONObject基本内容(二)

    参考内容:http://swiftlet.net/archives/category/json  十分感谢!!! 这部分的内容主要是讲述 javaBean转换为JSONObect时,如果有些属性不需要 ...

  10. &lbrack;java&rsqb;String和Date、Timestamp之间的转换

    一.String与Date(java.util.Date)互转  1.1 String -> Date Date date = DateFormat.parse(String  str); St ...