牛客挑战赛33 C 艾伦的立体机动装置(几何)
阅读原文时间:2023年07月08日阅读:2

思路:

我们需要枚举展开多少条边 然后把上底面的点放到和下底面一个平面 然后算两点之间的距离 注意判断直线与线段是否有交点

#include

using namespace std;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int N = 1e5+7;
//Compares a double to zero
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return-1;
else return 1;
}
//square of a double
inline double sqr(double x){return x*x;}

struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;
y = _y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
void output(){
printf("%.2f-%.2f\n",x,y);
}
bool operator == (Point b)const{
return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;
}
bool operator < (Point b)const{ return sgn(x-b.x)== 0-sgn(y-b.y)?0:x 0)return 2;
else return 3;
}
// 点在线段上的判断
bool pointonseg(Point p){
return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
}
//两向量平行 (对应直线平行或重合)
bool parallel(Line v){
return sgn((e-s)^(v.e-v.s)) == 0;
}
//两线段相交判断
//2 规范相交
//1 非规范相交
//0 不相交
int segcrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
int d3 = sgn((v.e-v.s)^(s-v.s));
int d4 = sgn((v.e-v.s)^(e-v.s));
if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
(d4==0 && sgn((e-v.s)*(e-v.e))<=0);
}
//直线和线段相交判断
//-*this line -v seg
//2 规范相交
//1 非规范相交
//0 不相交
int linecrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
if((d1^d2)==-2) return 2;
return (d1==0||d2==0);
}
//两直线关系
//0 平行
//1 重合
//2 相交
int linecrossline(Line v){
if((*this).parallel(v))
return v.relation(s)==3;
return 2;
}
//求两直线的交点
//要保证两直线不平行或重合
Point crosspoint(Line v){
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1
));
}
//点到直线的距离
double dispointtoline(Point p){
return fabs((p-s)^(e-s))/length();
}
//点到线段的距离
double dispointtoseg(Point p){
if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0)
return min(p.distance(s),p.distance(e));
return dispointtoline(p);
}
//返回线段到线段的距离
//前提是两线段不相交,相交距离就是 0 了
double dissegtoseg(Line v){
return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v
.dispointtoseg(s),v.dispointtoseg(e)));
}
//返回点 p 在直线上的投影
Point lineprog(Point p){
return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
}
//返回点 p 关于直线的对称点
Point symmetrypoint(Point p){
Point q = lineprog(p);
return Point(2*q.x-p.x,2*q.y-p.y);
}
};
double sum[N],ans=1e18;
int s,t;
void work(Point x,Line tmp,int i){
Line res=Line(x,p[t]);
//printf("%lf\n",res.length());
if(res.linecrossseg(tmp)!=0){
ans=min(ans,res.length());
}
}
int main(){
int n,h;
scanf("%d%d",&n,&h);
for(int i=0;i<n;i++){
p[i].input();
}
scanf("%d%d",&s,&t);
--s; --t;
for(int i=1;i<n;i++){
sum[i]=sum[i-1]+p[i-1].distance(p[i]);
}
double tot=sum[n]=sum[n-1]+p[n-1].distance(p[0]);
for(int i=0;i<n;i++){
Point x=p[i],y=p[(i+1)%n];
Point z=(x-y).rotleft();
z=z*(h*1.0/z.len());

    Point t=y+z;

    Line tmp=Line(t,t+z.rotleft());  
    //printf("%lf\\n",tot);  
    double len;  
    if(s>=i+1){  
        len=sum\[s\]-sum\[i+1\];  
    }else{  
        len=tot-sum\[i+1\]+sum\[s\];  
    }  
    Point l,r;  
    l=t+(tmp.e-tmp.s)/tmp.length()\*len;  
    r=t+(tmp.e-tmp.s)/tmp.length()\*(len-tot);  

// cout<<i<<" "<<r.x<<" "<<r.y<<endl;
work(l,Line(x,y),i);
work(r,Line(x,y),i);
}
printf("%.6lf\n",ans);
}