牛客挑战赛33 C 艾伦的立体机动装置（几何体的最短距离 三分）

本文主要是介绍牛客挑战赛33 C 艾伦的立体机动装置（几何体的最短距离 三分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

 

OJ题号

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

https://ac.nowcoder.com/acm/contest/1115/C

简单题意

中文题

正解思路

• 因为下表面是可以走的，所以不能直接算s点和t点展开的直线距离。
• 枚举经过下表面的每一条边，再在每条边上三分求出最短距离。注意最短距离的初始值要设为不经过下表面任何一条边的最短距离。

slen记录每个顶点到s点的距离，getdis是获得上表面或下表面的两点距离，finddis是获得如果经过下表面某个点的路程距离，tridiv三分。因为我的下标是从0开始的，所以s点是p[s-1]。

详细链接

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int s,t,n;
double ans,slen[100001],h;
pair<double,double>p[100001];
inline double getdis(pair<double,double>p1,pair<double,double>p2)
{return sqrt((p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second));
}
inline double finddis(pair<double,double>now,int l,int r)
{double len = min(slen[l]+getdis(p[l],now),slen[r]+getdis(p[r],now));return sqrt(h*h+len*len)+getdis(now,p[t-1]);
}
inline double tridiv(int l,int r)
{double minn = 0x3f3f3f3f;pair<double,double> left = p[l];pair<double,double> right = p[r];while(getdis(left,right)>1e-3){pair<double,double> first = make_pair((2*left.first+right.first)/3,(2*left.second+right.second)/3);pair<double,double> second = make_pair((left.first+2*right.first)/3,(left.second+2*right.second)/3);double firdis = finddis(first,l,r);double secdis = finddis(second,l,r);if(firdis>secdis){left = first;minn = min(minn,secdis);}else{right = second;minn = min(minn,firdis);}}return minn;
}
int main()
{scanf("%d%lf",&n,&h);for(int i = 0; i<n; i++)scanf("%lf%lf",&p[i].first,&p[i].second);scanf("%d%d",&s,&t);double s1 = 0,s2 = 0,sum = 0;int last = s-1;slen[last] = 0;for(int i = s%n; i!=s-1; i++,i%=n){double len = getdis(p[last],p[i]);sum+=len;slen[i] = slen[last]+len;last = i;}sum+=getdis(p[last],p[s-1]);for(int i = 0; i<n; i++)slen[i] = min(slen[i],sum-slen[i]);ans = sqrt(slen[t-1]*slen[t-1]+h*h);last = n-1;for(int i = 0; i<n; i++,last++,last%=n)ans = min(ans,tridiv(last,i));printf("%.6lf",ans);return 0;
}

 

 

 

 

 

点与线模板，但我不会用这个模板做这道题。

#include <bits/stdc++.h>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<b.x;}Point operator-(const Point &b)const{return Point(x-b.x,y-b.y);}//叉积double operator ^(const Point &b)const{return x*b.y-y*b.x;}//点积double operator *(const Point &b)const{return x*b.x + y*b.y;}//返回长度double len(){return hypot(x,y);//库函数}//返回长度的平方double len2(){return x*x + y*y;}//返回两点的距离double distance(Point p){return hypot(x-p.x,y-p.y);}Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}Point operator *(const double &k)const{return Point(x*k,y*k);}Point operator /(const double &k)const{return Point(x/k,y/k);}//计算 pa 和 pb 的夹角//就是求这个点看 a,b 所成的夹角//测试 LightOJ1203double rad(Point a,Point b){Point p = *this;return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) ));}//化为长度为 r 的向量Point trunc(double r){double l = len();if(!sgn(l))return *this;r /= l;return Point(x*r,y*r);}//逆时针旋转 90 度Point rotleft(){return Point(-y,x);}//顺时针旋转 90 度Point rotright(){return Point(y,-x);}//绕着 p 点逆时针旋转 anglePoint rotate(Point p,double angle){Point v = (*this)-p;double c = cos(angle), s = sin(angle);return Point(p.x + v.x*c-v.y*s,p.y + v.x*s + v.y*c);}
}p[N];
struct Line{Point s,e;
Line(){}Line(Point _s,Point _e){s = _s;e = _e;}bool operator ==(Line v){return (s == v.s)&&(e == v.e);}//根据一个点和倾斜角 angle 确定直线,0<=angle<piLine(Point p,double angle){s = p;if(sgn(angle-pi/2) == 0){e = (s + Point(0,1));}else{e = (s + Point(1,tan(angle)));}}//ax+by+c=0Line(double a,double b,double c){if(sgn(a) == 0){s = Point(0,-c/b);e = Point(1,-c/b);}else if(sgn(b) == 0){s = Point(-c/a,0);e = Point(-c/a,1);}else{s = Point(0,-c/b);e = Point(1,(-c-a)/b);}}void input(){s.input();e.input();}void adjust(){if(e < s){swap(s,e);}}//求线段长度double length(){return s.distance(e);}//返回直线倾斜角 0<=angle<pidouble angle(){double k = atan2(e.y-s.y,e.x-s.x);if(sgn(k) < 0)k += pi;if(sgn(k-pi) == 0)k-= pi;return k;}//点和直线关系//1 在左侧//2 在右侧//3 在直线上int relation(Point p){int c = sgn((p-s)^(e-s));if(c < 0)return 1;else if(c > 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);
}

 

这篇关于牛客挑战赛33 C 艾伦的立体机动装置（几何体的最短距离 三分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---