题解 | #[SCOI2010]传送带#
[SCOI2010]传送带
https://ac.nowcoder.com/acm/problem/20276
对CD来说进早了可能因为路远，时间增大，进晚了因为没有省力所以时间增大，故区间是一个凹状的，可以使用三分去解决。对于何时进入CD也是一样的。故嵌套三分的做法。
但因为本题针对实数的运算，所以要求精度。至于为什么要在计算距离时加上精度，我想是因为在求距离过程中小数位会有所丢失的原因吧。所以需要加上（当然这只是我的想法）。
按雨巨的另一种做法，直接固定循环次数也可以。
#include <bits/stdc++.h>
using namespace std;
struct Node{
double x;
double y;
} a,b,c,d, ab, cd;
double P,Q,R;
const double eqs = 1e-8;
double dist(Node a, Node b) {
return sqrt(1e-11+pow(a.x-b.x, 2)+pow(a.y-b.y, 2));
}
double calc2(double m) {
cd.x = c.x+(m/dist(c, d)*(d.x-c.x));
cd.y = c.y+(m/dist(c, d)*(d.y-c.y));
double time1 = dist(ab, cd)/R;
double time2 = dist(cd, d)/Q;
return time1+time2;
}
double calc(double m)
{
ab.x = a.x+(m/dist(a,b)*(b.x-a.x));
ab.y = a.y+(m/dist(a,b)*(b.y-a.y));
double time1 = m/P;
double l = 0, r = dist(c, d);
double ans = 10000;
while (r-l>eqs) {
double m1 = l+(r-l)/3;
double m2 = r-(r-l)/3;
if (calc2(m2)-calc2(m1)>eqs) {
ans = calc2(m1);
r = m2;
} else {
ans = calc2(m2);
l = m1;
}
}
return ans+time1;
}
int main() {
cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
cin>>P>>Q>>R;
double ans = 1000;
double l=0, r = dist(a, b);
while (r-l>eqs) {
double m1 = l+(r-l)/3;
double m2 = r-(r-l)/3;
if (calc(m2)-calc(m1)>eqs) {
ans = calc(m1);
r = m2;
} else {
ans = calc(m2);
l = m1;
}
}
printf("%.2lf", ans);
return 0;
}
投递hulu等公司7个岗位
我还在畏畏缩缩准备八股算法
，那举办了