题意简述
多测。给定若干条线段，全部与\(x\)轴平行。
其中有\(2\)条线段表示房子和人行道（虽然翻译不是人行道就是了），保证房子在人行道上面。
其他线段表示障碍物（不保证在房子和人行道之间）。
请找出人行道上最长的连续部分，使得在这中间可以完整地看到房子的全貌。
如果存在，输出其长度即可，保留\(2\)位小数；如果不存在输出No View。
数据范围没给，不过开\(10^5\)能过。具体输入格式见题目。
思路分析
先以人行道的左端点为\((0,0)\)，将所有坐标整体移动一下，方便考虑。
我们发现想直接计算能看到的区域比较困难，但是可以计算出每个障碍物形成的盲区：
如图，盲区就是房子的左右端点和障碍物的右左端点（注意顺序）连接并延长，与人行道相交形成的线段。
我们对每个障碍物，计算盲区的左右端点（计算射线和直线的交点，具体见代码）并储存。注意盲区的左右端点可能超出边界，所以需要取一下\(\min,\max\)。
我们注意到盲区可能发生重叠，所以需要把重叠部分进行合并，方便计算。
具体方法嘛，就是把盲区按左端点从小到大排序。如果后一个盲区的左端点\(<\)前一个盲区的右端点，就更新前一个盲区的右端点，并且删除后一个盲区。代码使用STL的链表实现。
合并完再遍历一遍，计算最大值即可求出答案。注意遍历前还需要把\((0,0),(len,len)\)分别加到链表的头和尾，因为左右边界也可能存在非盲区。
就酱。
思路并不难，不过代码实现有一些细节需要注意：
-
盲区左右端点可能超出边界，需要取一下\(\min,\max\)。
-
合并完盲区，需要额外把\((0,0),(len,len)\)分别加到链表的开头和结尾。
-
对于所有障碍物，如果其\(y\)坐标\(\ge\)房子的\(y\)坐标，或者\(<\)人行道的\(y\)坐标，就不能参与考虑。注意这一判断与\(x\)坐标无关，就算障碍物完全在人行道外面，也可能在人行道上形成盲区。
-
遍历链表的过程中，可能会有删除操作。因此我们需要注意一下使用迭代器的方式：
for(auto it=lis.begin();it!=lis.end();){ if(/* 条件 */){ /* Something ... */ it=segs.erase(it); }else{ /* Something ... */ it++; } } -
保留\(2\)位小数。
Code
POJ的编译器太老了，提交的代码需要经过一番修改。这里就不放修改后的代码了，毕竟重在理解嘛。
点击查看代码
#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct tseg{double x1,x2,y;};
struct point{double x,y;};
tseg house,lin;
int n,siz;
double ans;
void modify(tseg &a){
a.x1-=lin.x1,a.x2-=lin.x1,a.y-=lin.y;
}//将a的绝对位置转为相对人行道的位置
list<pair<double,double>> segs;
double calc(point a,point b){
return a.x-a.y*(a.x-b.x)/(a.y-b.y);
}//计算射线AB与x轴的交点
int main(){
while(cin>>house.x1>>house.x2>>house.y){
segs.clear(),ans=0;
if(house.x1==house.x2&&house.x2==house.y&&house.y==0) break;
cin>>lin.x1>>lin.x2>>lin.y>>n;
modify(house);
double len=lin.x2-lin.x1;
for(int i=1;i<=n;i++){
tseg ta;
cin>>ta.x1>>ta.x2>>ta.y;
modify(ta);
if(ta.y>=house.y||ta.y<0) continue;
double x1=calc({house.x1,house.y},{ta.x2,ta.y});
double x2=calc({house.x2,house.y},{ta.x1,ta.y});
segs.push_back({min(len,max(0.0,x2)),min(len,max(0.0,x1))});
}//注意x1,x2需要反序，x2实际是左端点
segs.sort();
for(auto it=segs.begin(),lastit=segs.end();it!=segs.end();){
if(lastit!=segs.end()&&(*lastit).second>=(*it).first){
(*lastit).second=max((*lastit).second,(*it).second);
it=segs.erase(it);
}else lastit=it,it++;
}//合并盲区，注意特殊的迭代器写法
segs.push_front({0,0});
segs.push_back({len,len});
for(auto it=segs.begin(),lastit=segs.end();it!=segs.end();lastit=it,it++){
if(it==segs.begin()) continue;
ans=max(ans,(*it).first-(*lastit).second);
}
if(ans==0) cout<<"No View\n";
else cout<<fixed<<setprecision(2)<<ans<<"\n";
}
return 0;
}