题解：CF1468G Hobbits

· · 题解

解题思路

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

特别地，最后一个线段一定能够被照到，因此可以直接计算，并令 k=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=read(),h=read();
    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;
}