AtCoder ABC 365G 凸包 + 二分

本文主要是介绍AtCoder ABC 365G 凸包 + 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

AtCoder ABC 365G Freestyle

题解

考虑任两种操作 $A_{i},B_{i})$ 和 $A_{j},B_{j})$ ，则他们的任意组合可以表示为 $tA_{i}+(1-t)A_{j},tB_{i}+(1-t)B_{j}\big)$ ，那么将其看作二维平面的点，即 $x = B, y = A$ ，则这两种操作对应点的连线都可以被取到。拓展到两个点以上的情况，则可以任取这些点构成的凸包内的任一点。

对于约束 $\leq 0$ ，则可以取使得 $y / x$ 最小的节点 $s$ ，若此节点不满足约束条件，则任一节点都不满足条件。对于最小化时间，则转化为最大化 $x$ ，那么可以取使 $x$ 最大化的节点 $t$ ，若 $t$ 满足约束条件，则单位为 $t$ 对应的时间。

其余情况，我们考虑凸包 $s\rightarrow t$ 的节点，二分满足约束条件的节点，最后再二分该节点与凸包上次一节点的线性组合。总时间复杂度 $q\log n)$ 。

#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Point {T x, y;Point operator+(Point rhs) {return {x + rhs.x, y + rhs.y};}Point operator-(Point rhs) {return {x - rhs.x, y - rhs.y};}T dot(Point rhs) {return x * rhs.x + y * rhs.y;}T det(Point rhs) {return x * rhs.y - y * rhs.x;}
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;using P = Point<long long>;vector<P> ps(n);for (int i = 0; i < n; ++i) {cin >> ps[i].y >> ps[i].x;}auto get_convex_hull = [&]() {sort(ps.begin(), ps.end(), [&](const auto& lhs, const auto& rhs) {if (lhs.x != rhs.x) {return lhs.x < rhs.x;}return lhs.y < rhs.y;});vector<P> qs(n * 2);int k = 0;for (int i = 0; i < n; ++i) {while (k > 1 && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0) {k -= 1;}qs[k++] = ps[i];}for (int i = n - 2, t = k; i >= 0; --i) {while (k > t && (qs[k - 1] - qs[k - 2]).det(ps[i] - qs[k - 1]) <= 0) {k -= 1;}qs[k++] = ps[i];}qs.resize(k - 1);return qs;};if (n > 1) {ps = get_convex_hull();n = ps.size();}int s = -1, t = -1;for (int i = 0; i < n; ++i) {if (s == -1 || ps[i].y * ps[s].x < ps[s].y * ps[i].x) {s = i;}if (t == -1 || ps[t].x < ps[i].x) {t = i;}}int q;cin >> q;while (q--) {int c, d;cin >> c >> d;auto judge = [&](P& p) {return d * p.y - c * p.x <= 0;};if (!judge(ps[s])) {cout << -1 << '\n';continue;}if (judge(ps[t])) {cout << fixed << setprecision(11) << (double)d / ps[t].x << '\n';continue;}auto get_idx = [&]() {int lb = s, ub = t;while (ub - lb > 1) {int mid = (lb + ub) / 2;if (judge(ps[mid])) {lb = mid;} else {ub = mid;}}return lb;};int idx = get_idx();double lb = 0, ub = 1;for (int i = 0; i < 50; ++i) {double mid = (lb + ub) / 2;double x = ps[idx].x + (ps[(idx + 1) % n].x - ps[idx].x) * mid;double y = ps[idx].y + (ps[(idx + 1) % n].y - ps[idx].y) * mid;if (d * y - c * x <= 0) {lb = mid;} else {ub = mid;}}double x = ps[idx].x + (ps[(idx + 1) % n].x - ps[idx].x) * lb;cout << fixed << setprecision(11) << d / x << '\n';}return 0;
}