三分套三分入门题……

策略肯定是从A走到AB上一点，然后再走到CD上的一个点，再向D走。

很显然答案函数是一个关于那两个点下凸的东西（不会证？GeoGebra之类的东西画一下就好啦！还不如像我这样口胡），所以我们可以先对第一维三分，然后套上对第二维的三分……

代码：

/**************************************************************
	Problem: 1857
	User: danihao123
	Language: C++
	Result: Accepted
	Time:244 ms
	Memory:820 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <cmath>
typedef double R;
const R eps = 1e-6;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) return -1;
    else return 1;
  }
}
struct Point {
  R x, y;
  Point(R qx = 0, R qy = 0) {
    x = qx; y = qy;
  }
};
typedef Point Vector;
Vector operator +(const Vector &a, const Vector &b) {
  return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
  return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(R x, const Vector &v) {
  return Point(v.x * x, v.y * x);
}
Vector operator *(const Vector &v, R x) {
  return Point(v.x * x, v.y * x);
}
R dot(const Vector &a, const Vector &b) {
  return a.x * b.x + a.y * b.y;
}
R times(const Vector &a, const Vector &b) {
  return a.x * b.y - a.y * b.x;
}
R dist(const Point &a, const Point &b) {
  return sqrt(dot(a - b, a - b));
}
bool cmp(const Point &a, const Point &b) {
  if(sign(a.x - b.x) == 0) {
    return a.y < b.y;
  } else {
    return a.x < b.x;
  }
}
Point A, B, C, D;
R p, q, r;
Vector D_AB, D_DC;
R f(const Point &AB, const Point &CD) {
  return (dist(AB, A) / p + dist(CD, D) / q + dist(AB, CD) / r);
}
R F(Point AB) {
  R L = 0, R = 1;
  int T = 200;
  while(T --) {
    double M1 = L + (R - L) / 3;
    double M2 = R - (R - L) / 3;
    Point P1 = D + M1 * D_DC;
    Point P2 = D + M2 * D_DC;
    double f1 = f(AB, P1), f2 = f(AB, P2);
    if(f1 < f2) {
      R = M2;
    } else {
      L = M1;
    }
  }
  return f(AB, D + L * D_DC);
}
R solve() {
  R L = 0, R = 1;
  int T = 200;
  while(T --) {
    double M1 = L + (R - L) / 3;
    double M2 = R - (R - L) / 3;
    Point P1 = A + M1 * D_AB;
    Point P2 = A + M2 * D_AB;
    double F1 = F(P1), F2 = F(P2);
    if(F1 < F2) {
      R = M2;
    } else {
      L = M1;
    }
  }
  return F(A + L * D_AB);
}

int main() {
  scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y);
  scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y);
  scanf("%lf%lf%lf", &p, &q, &r);
  D_AB = B - A; D_DC = C - D;
  printf("%.2lf\n", solve());
  return 0;
}

• 相关文章
• 全局相关文章