Bzoj 1857(三分套三分)

BZOJ 1857
题意:见上。
观察(生活经验)发现,在 $ AB $ 上肯定存在一个点,他左移右移都会增大答案,所以是个单峰函数,同理 $ CD $ 。所以我们写一个三分套三分,即三分完以后再用这个三分结果进行下一个三分操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
#define db double
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
namespace flyinthesky {
const db eps = 1e-10;
int ax, ay, bx, by, cx, cy, dx, dy, p, q, r;
db dist(db xa, db ya, db xb, db yb) {return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));}
db calc(db Ux, db Uy, db Dx, db Dy) {
db U = dist(ax, ay, Ux, Uy) / (db)p;
db D = dist(Dx, Dy, dx, dy) / (db)q;
db H = dist(Ux, Uy, Dx, Dy) / (db)r;
return U + D + H;
}
db f(db Ux, db Uy) {
db lx_2 = cx, rx_2 = dx;
db ly_2 = cy, ry_2 = dy;
for (int i = 1; i <= 300; ++i) {
db midx_2 = (lx_2 + rx_2) / 2.0;
db midy_2 = (ly_2 + ry_2) / 2.0;
db mmidx_2 = (midx_2 + rx_2) / 2.0;
db mmidy_2 = (midy_2 + ry_2) / 2.0;
if (calc(Ux, Uy, midx_2, midy_2) - calc(Ux, Uy, mmidx_2, mmidy_2) > eps) lx_2 = midx_2, ly_2 = midy_2;
else rx_2 = mmidx_2, ry_2 = mmidy_2;
}
return calc(Ux, Uy, lx_2, ly_2);
}
void clean() {
}
int solve() {
scanf("%d%d%d%d%d%d%d%d%d%d%d", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy, &p, &q, &r);
clean();
db lx_1 = ax, rx_1 = bx;
db ly_1 = ay, ry_1 = by;
for (int i = 1; i <= 300; ++i) {
db midx_1 = (lx_1 + rx_1) / 2.0;
db midy_1 = (ly_1 + ry_1) / 2.0;
db mmidx_1 = (midx_1 + rx_1) / 2.0;
db mmidy_1 = (midy_1 + ry_1) / 2.0;
if (f(midx_1, midy_1) - f(mmidx_1, mmidy_1) > eps) lx_1 = midx_1, ly_1 = midy_1;
else rx_1 = mmidx_1, ry_1 = mmidy_1;
}
printf("%.2f\n", f(lx_1, ly_1));
return 0;
}
};
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------