题解：CF1468G Hobbits

原题链接

• 洛谷 CF1468G Hobbits

解题思路

某个点能被光源照到，当且仅当从光源 $L$ 到该点之间没有被遮挡，即不存在其他点的斜率小于该点。因此，我们可以从后往前推，维护斜率最小的点 $a_k$。

特别地，最后一个线段一定能够被照到，因此可以直接计算，并将 $k \gets n-1$。

接下来对于每条线段 $a_ia_{i+1}$ 分类讨论：

1. 如果线段 $a_iL$ 的斜率大于 $a_kL$，说明该线段的左端点不能被光源照到，整个线段都无法被照到。
2. 求出线段 $a_ia_{i+1}$ 与线段 $a_kL$ 的交点 $P$，交点 $P$ 上方的线段 $a_iP$ 可以被光源照到。
3. 特别地，如果线段 $a_iL$ 的斜率等于线段 $a_{i+1}L$ 的斜率，表示该线段与光线重叠，整个线段都会被光源照到。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const double eps=1e-10;
const int N=200005;
int sgn(double x){return (x>eps)-(x<-eps);}
struct Point
{
	double x,y;
}a[N];
double Dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
double Slope(Point A,Point B){return (A.y-B.y)/(A.x-B.x);}
Point Cross(Point A,Point B,Point C,Point D)
{
	double a1=A.y-B.y,b1=B.x-A.x,c1=A.x*B.y-B.x*A.y;
	double a2=C.y-D.y,b2=D.x-C.x,c2=C.x*D.y-D.x*C.y;
	return {(b1*c2-b2*c1)/(a1*b2-a2*b1),(a2*c1-a1*c2)/(a1*b2-a2*b1)};
}
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
int main()
{
	int n,h;
	cin>>n>>h;
	for(int i=1;i<=n;i++)
	{
		a[i].x=read();
		a[i].y=read();
	}
	Point L={a[n].x,a[n].y+h};
	int k=n-1;
	double ans=Dis(a[n-1],a[n]);
	for(int i=n-2;i>=1;i--)
	{
		if(sgn(Slope(a[i],L)-Slope(a[k],L))>0)continue;
		ans+=Dis(a[i],sgn(Slope(a[i],L)-Slope(a[i+1],L))==0?a[i+1]:Cross(a[i],a[i+1],a[k],L));
		k=i;
	}
	cout<<fixed<<setprecision(10)<<ans<<'\n';
	return 0;
}