2021 联想杯 E
Experiment Class
https://ac.nowcoder.com/acm/contest/17574/E
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; }