博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ2074:Line of Sight——题解
阅读量:7044 次
发布时间:2019-06-28

本文共 941 字,大约阅读时间需要 3 分钟。

题目大意:(下面的线段都与x轴平行)给两条线段,一个点在其中一条线段看另一条线段,但是中间有很多线段阻挡视线。求在线段上最大连续区间使得在上面的点都能看见另一条线段。

——————————————

这题的思路很简单,首先根据左端点先排个序,然后找前一条线段的右端点和房子左端点连,后一条线段的左端点和房子右端点连,那么两条连线与路的交的范围即是可行解。

但是debug真的累……好在poj有神犇提供了部分debug数据,经过多次尝试,发现:

1.筛除不在路和房子之间的线段。

2.可行解区域可能超过路。

3.线段可能互相遮挡。

第三条蛮麻烦的,一个简单粗暴的比较方法就是枚举所有线段,判断是否有和线段相交,如果相交则更换为该线段的左/右端点。

#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef double dl;const int INF=2147483647;const int N=201;struct point{ //既是向量又是点 dl x; dl y;};struct line{ dl x1; dl x2; dl y;}p[N],st,ed;bool cmp(line a,line b){ return (a.x1
=1;i--){ if(p[i].y>st.y||p[i].y
st.y||p[i].y
st.y||p[j].y
st.y||p[j].y
ed.x2)r=ed.x2; maxn=max(maxn,r-l); } } if(maxn==0){ puts("No View"); }else{ printf("%.2f\n",maxn); } } return 0;}

 

转载于:https://www.cnblogs.com/luyouqi233/p/8067595.html

你可能感兴趣的文章
WebAssembly Studio:Mozilla提供的WASM工具
查看>>
Visual Studio 15改进C++工程加载
查看>>
雷军定AI+IoT为小米核心战略,牵手宜家推进生态布局
查看>>
移动开发的罗曼蒂克消亡史
查看>>
独家解读 | 滴滴机器学习平台架构演进之路
查看>>
Kotlin语言1.0Beta发布,JetBrain介绍其设计理念
查看>>
继爆款超级账本后,IBM再次推出新产品
查看>>
“亲切照料”下的领域驱动设计
查看>>
在大规模系统中使用Scala
查看>>
资本冬天已至,开发者却可以着眼未来
查看>>
中国互联网公司开源项目调研报告
查看>>
百度启动高管退休计划,总裁张亚勤今年十月退休
查看>>
Entity Framework 6.3 和EF Core 3.0路线图
查看>>
《敏捷时代》作者访谈录
查看>>
Scrum Guides 2017年最新修改
查看>>
Cling旨在提供一款高性能的C++ REPL
查看>>
关于《在Windows与.NET平台上的持续交付实践》的问答录
查看>>
TensorFlow模型的签名推荐与快速上线\n
查看>>
改变的六条规则
查看>>
GitHub是如何改进自身的DNS架构的
查看>>