【BZOJ 1857】【SCOI 2010】传送带

三分套三分，虽然简单，但是也得掌握，，，

时间复杂度$O(log_{1.5}^2 n)$

一开始WA好几次发现是快速读入里没有return，这样也能过样例？_(:3J∠)_

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const double eps = 1e-3;

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

double p, q, r;

struct Point {

	double x, y;

} A1, A2, B1, B2;

double sqr(double x) {return x * x;}

double dis(Point A, Point B) {return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));}

double cal(Point B) {

	double c1, c2;

	Point P1 = B1, P2 = B2, x1, x2;

	while (fabs(P1.x - P2.x) > eps || fabs(P1.y - P2.y) > eps) {

		x1 = (Point) {P1.x + (P2.x - P1.x) / 3, P1.y + (P2.y - P1.y) / 3};

		x2 = (Point) {P1.x + (P2.x - P1.x) * 2 / 3, P1.y + (P2.y - P1.y) * 2 / 3};

		c1 = dis(B, x1) / r + dis(x1, B2) / q, c2 = dis(B, x2) / r + dis(x2, B2) / q;

		if (c1 < c2) P2 = x2;

		else P1 = x1;

	}

	return dis(B, P1) / r + dis(P1, B2) / q;

}

int main() {

	A1.x = in(); A1.y = in(); A2.x = in(); A2.y = in();

	B1.x = in(); B1.y = in(); B2.x = in(); B2.y = in();

	p = in(); q = in(); r = in();

	double c1, c2;

	Point P1 = A1, P2 = A2, x1, x2;

	while (fabs(P1.x - P2.x) > eps || fabs(P1.y - P2.y) > eps) {

		x1 = (Point) {P1.x + (P2.x - P1.x) / 3, P1.y + (P2.y - P1.y) / 3};

		x2 = (Point) {P1.x + (P2.x - P1.x) * 2 / 3, P1.y + (P2.y - P1.y) * 2 / 3};

		c1 = dis(A1, x1) / p + cal(x1), c2 = dis(A1, x2) / p + cal(x2);

		if (c1 < c2) P2 = x2;

		else P1 = x1;

	}

	printf("%.2lf\n", dis(A1, P1) / p + cal(P1));

	return 0;

}

期末考试Bless All！