Line of Sight题意 在房子和人行道之间有若干障碍物，它们都是用线段表示的，且都平行于x轴，问在人行道上能看到整个房子的最大连续长度是多少？思路 数据中有障碍物不在房子和人行道之间的情况，这种情况不用考虑。这道题直接求答案不好求，我们可以逆着思考，先把由每个障碍物挡住的连续区间求出来，然后在总的人行道上找出没有被这些区间覆盖的最长的连续区间就是答案了。 求一个障碍物挡住的区间： 代码
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std
;
typedef long long ll
;
typedef unsigned long ul
;
typedef unsigned long long ull
;
#define pi acos(-1.0)
#define e exp(1.0)
#define pb push_back
#define mk make_pair
#define fir first
#define sec second
#define scf scanf
#define prf printf
typedef pair
<ll
,ll
> pa
;
const int dir_4
[4][2]={-1,0,0,1,1,0,0,-1};
const int dir_8
[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int MAX_N
=1e7+7;
const double eps
=1e-8;
struct Pos
{
double x
,y
;
};
struct Seg
{
Pos pos_l
,pos_r
;
}obs
[MAX_N
],Hou
,Pl
;
struct node
{
double lx
,rx
;
bool operator
<(const node
&b
)const{
if(lx
!=b
.lx
)
return lx
<b
.lx
;
return rx
<b
.rx
;
}
}nm
[MAX_N
];
double do_x(double y
,Pos a
,Pos b
){
double x
=(b
.x
-a
.x
)*(y
-a
.y
)/(b
.y
-a
.y
)+a
.x
;
return x
;
}
int N
;
int main()
{
int i
,j
,k
;
double a
,b
,c
;
while(scf("%lf %lf %lf",&a
,&b
,&c
)&&!(fabs(a
)<eps
&&fabs(b
)<eps
&&fabs(c
)<eps
)){
Hou
={Pos
{a
,c
},Pos
{b
,c
}};
scf("%lf %lf %lf",&a
,&b
,&c
);
Pl
={Pos
{a
,c
},Pos
{b
,c
}};
scf("%d",&N
);
int cnt
=0;
double maxx
=max(Hou
.pos_l
.y
,Pl
.pos_l
.y
);
double minn
=min(Hou
.pos_l
.y
,Pl
.pos_l
.y
);
for(i
=0;i
<N
;i
++){
scf("%lf %lf %lf",&a
,&b
,&c
);
if(c
<maxx
&&fabs(maxx
-c
)>eps
&&c
>minn
&&fabs(c
-minn
)>eps
)
obs
[cnt
++]={Pos
{a
,c
},Pos
{b
,c
}};
}
N
=cnt
;
double res
=0,x1
,x2
;
for(i
=0;i
<N
;i
++){
x1
=do_x(Pl
.pos_l
.y
,Hou
.pos_r
,obs
[i
].pos_l
);
x2
=do_x(Pl
.pos_l
.y
,Hou
.pos_l
,obs
[i
].pos_r
);
nm
[i
]=node
{x1
,x2
};
}
double pre
=Pl
.pos_l
.x
;
sort(nm
,nm
+N
);
for(i
=0;i
<N
;i
++){
if(nm
[i
].lx
>pre
){
res
=max(res
,nm
[i
].lx
-pre
);
pre
=nm
[i
].rx
;
}
else
pre
=max(pre
,nm
[i
].rx
);
}
if(Pl
.pos_r
.x
>pre
)
res
=max(res
,Pl
.pos_r
.x
-pre
);
if(fabs(res
)<eps
)
puts("No View");
else
prf("%.2f\n",res
);
}
return 0;
}
