E
题意略。
本题先枚举是先去第一条线还是第二条线,再三分套三分也能过。
但究竟为啥能呢?我并没有太看出来这个问题具有什么凸性质 ...
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
double a, b, c, d, xx0, xx1, yy0, yy1;
void init(){
a = read(), b = read(), c = read(), d = read();
xx0 = read(), yy0 = read(), xx1 = read(), yy1 = read();
}
inline double distot1(double sf1, double sf2){
return hypot(xx0 - a * sf1, yy0 - b * sf1) + hypot(a * sf1 - c * sf2, b * sf1 - d * sf2) +
hypot(xx1 - c * sf2, yy1 - d * sf2);
}
inline double distot2(double sf1, double sf2){
return hypot(xx1 - a * sf1, yy1 - b * sf1) + hypot(a * sf1 - c * sf2, b * sf1 - d * sf2) +
hypot(xx0 - c * sf2, yy0 - d * sf2);
}
double calc1(double sf1){
double lb2 = 0.0, rb2 = 1e3;
REP(T, 1, 50){
double len = (rb2 - lb2) / 3;
double mid = lb2 + len;
double mid2 = rb2 - len;
if (distot1(sf1, mid) < distot1(sf1, mid2))
rb2 = mid2;
else lb2 = mid;
}
return distot1(sf1, lb2);
}
double calc2(double sf1){
double lb2 = 0.0, rb2 = 1e3;
REP(T, 1, 50){
double len = (rb2 - lb2) / 3;
double mid = lb2 + len;
double mid2 = rb2 - len;
if (distot2(sf1, mid) < distot2(sf1, mid2))
rb2 = mid2;
else lb2 = mid;
}
return distot2(sf1, lb2);
}
void solve(){
double dis1 = hypot(a, b);
double dis2 = hypot(c, d);
a /= dis1, b /= dis1;
c /= dis2, d /= dis2;
double ans = 1e7;
double lb1 = 0.0, rb1 = 1e3;
REP(T1, 1, 50){
double len = (rb1 - lb1) / 3;
double mid = lb1 + len;
double mid2 = rb1 - len;
if (calc1(mid) < calc1(mid2))
rb1 = mid2;
else lb1 = mid;
// cout << lb1 << " " << rb1 << endl;
}
ans = min(ans, calc1(lb1));
lb1 = 0.0, rb1 = 1e3;
REP(T1, 1, 50){
double len = (rb1 - lb1) / 3;
double mid = lb1 + len;
double mid2 = rb1 - len;
if (calc2(mid) < calc2(mid2))
rb1 = mid2;
else lb1 = mid;
}
ans = min(ans, calc2(lb1));
printf("%.3lf\n", ans);
}
int main(){
int T = 1;
while (T--){
init();
solve();
}
return 0;
} 
京公网安备 11010502036488号