题目链接
在房屋与property line之间有障碍物(房屋,property line,障碍物均可看做与x轴平行的线段)
求从房屋到property line最长的能看到的一段的长度
能看到的一段的长度本身并不好求解
但是不能看到的一段的长度却相对好求解
于是找到property line上看不见的每一段
而后按照左端点排序,乱搞即可
边界情况
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e4+5;
const double eps=1e-7;
struct sec{double l,r;}a[N];
bool operator<(sec x,sec y){return x.l<y.l;}
struct point{double x,y;};
point e1=(point){0,0},e2=(point){50,0};
double ans;
point operator-(point x,point y){return (point){x.x-y.x,x.y-y.y};}
double operator^(point x,point y){return x.x*y.y-x.y*y.x;}
struct seg{point u,v;}hs,pro;
inline double inc(point p1,point p2)
{
double s1=(e1-p1)^(e2-p1),s2=(e2-p2)^(e1-p2);
return p2.x+(p1.x-p2.x)*s2/(s1+s2);
}
int main()
{
while(7)
{
ans=0;
scanf("%lf%lf%lf",&hs.u.x,&hs.v.x,&hs.u.y);
hs.v.y=hs.u.y;
if(hs.u.x<eps&&hs.v.x<eps&&hs.u.y<eps)break;
scanf("%lf%lf%lf",&pro.u.x,&pro.v.x,&pro.u.y);
pro.v.y=pro.u.y;e1.y=e2.y=pro.u.y;
int num=0,cnt=0;scanf("%d",&num);
for(int i=1;i<=num;++i)
{
double x1=0,x2=0,y=0;
scanf("%lf%lf%lf",&x1,&x2,&y);
if(y-hs.u.y>-eps||pro.u.y-y>-eps)continue;
a[++cnt].l=inc(hs.u,(point){x2,y});
a[cnt].l=min(pro.v.x,max(pro.u.x,a[cnt].l));
a[cnt].r=inc(hs.v,(point){x1,y});
a[cnt].r=min(pro.v.x,max(pro.u.x,a[cnt].r));
swap(a[cnt].l,a[cnt].r);
}
if(!cnt){printf("%.2f\n",pro.v.x-pro.u.x);continue;}
sort(a+1,a+cnt+1);
double ll=-1,rr=-1;
for(int i=1;i<=cnt;++i)
{
if(ll<-eps&&rr<-eps)
{
ll=a[i].l,rr=a[i].r;
ans=max(ans,ll-pro.u.x);
continue;
}
if(rr-a[i].l>-eps)rr=max(rr,a[i].r);
else
{
ans=max(ans,a[i].l-rr);
ll=a[i].l,rr=a[i].r;
}
}
ans=max(ans,pro.v.x-rr);
if(ans<eps)puts("No View");
else printf("%.2f\n",ans);
}
return 0;
}
原文:https://www.cnblogs.com/zmyzmy/p/12220847.html