牛客挑战赛33 C 艾伦的立体机动装置

题意

给出一个多边柱体，从上底面的边缘的一点走到下底面边缘的一点，要求不能经过上底面，求最小距离

题解

首先，侧面展开是一个长方形，如果不能走下底面的话，就是一个长方形上两点的直线距离
现在可以经过下底面
那么，侧面和下底面的展开图会有很多可能，枚举下底面相连的底边，计算即可。

侧面展开时，假设线段 $(i, i + 1)$ 与底边重合，我们要确定展开后点 s 的位置，首先计算出 $i - > s$ 的逆时针距离，即线段 $i - k$
点 $s^{'}$ 的坐标就是点 k 的坐标旋转 $α$ 角度的位置
需要注意的是，如果 $s^{'} - t$ 经过线段 $(i, i + 1)$ ，答案就是直线距离，否则就是两条折线的距离之和
最后反方向展开再算一遍

代码

#include<bits/stdc++.h>
#define N 100010
#define eps 1e-5
#define pi 3.141592653589793
#define sc(x) scanf("%d",&x)
using namespace std;
int dcmp(double x){if (fabs(x)<eps)return 0;else return x<0?-1:1;}
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){ }
    void read(){scanf("%lf%lf",&x,&y);}
}a[N];
typedef Point Vector;

Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator / (Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator == (Vector a,Vector b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}  //点积
double Length(Vector a){return sqrt(Dot(a,a));}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
Point Normal(Point a){ return a/Length(a); }
Vector Rotate(Vector a,double rad)// 向量 a 逆时针旋转 rad
{return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
//线段相交判定，不包含端点,相交返回 1，不交返回 0，当包含端点为<=
bool SPI(Point a1,Point a2,Point b1,Point b2)
{
    double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
           c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
    return dcmp(c1)*dcmp(c2)<=0 && dcmp(c3)*dcmp(c4)<=0;
}

double h,d[N]; int n,s,t;

double get(int a,int b){
    if (a<=b) return d[b]-d[a];
    return d[n]+d[b]-d[a];
}

double f(double x){return sqrt(x*x+h*h); }

int main(int argc, char const *argv[])
{
    sc(n); scanf("%lf",&h);
    for(int i=0;i<n;i++) a[i].read();
    for(int i=1;i<=n;i++) d[i]=d[i-1]+Length(a[i-1]-a[i%n]);
    scc(s,t); s--,t--;  
    double ans=1e18;
    for(int i=0;i<n;i++){
        int j=(i+1)%n;
        double dis=get(i,s);
        Point r=Rotate(Normal(a[j]-a[i])*f(dis),pi*2-atan(h/dis))+a[i];
        if (SPI(r,a[t],a[i],a[j])) ans=min(ans,Length(r-a[t]));else
        ans=min(ans,min(Length(r-a[i])+Length(a[i]-a[t]),Length(r-a[j])+Length(a[j]-a[t])));

        dis=d[n]-dis+Length(a[i]-a[j]);
        r=Rotate(Normal(a[i]-a[j])*f(dis),atan(h/dis))+a[j];
        if (SPI(r,a[t],a[i],a[j])) ans=min(ans,Length(r-a[t]));else
        ans=min(ans,min(Length(r-a[i])+Length(a[i]-a[t]),Length(r-a[j])+Length(a[j]-a[t])));
    }
    printf("%.5f\n",ans);
    return 0;
}