↵
<spoiler summary="
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define ld long double↵
#define fi first↵
#define se second↵
#define pb push_back↵
#pragma GCC optimize("unroll-loops,O3")↵
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")↵
#define cok cout << (ok ? "YES\n" : "NO\n");↵
#define dbg(x) cout << (#x) << ": " << x << endl;↵
#define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii<r;ii++) cout << x[ii] << " "; cout << endl;↵
#define int long long↵
#define pi pair<int, int>↵
const int N = 1e6+9;↵
int n, q;↵
struct pt {↵
int x, y;↵
pt operator-(pt b) {return {x - b.x, y - b.y};}↵
int operator%(pt b) {return x * b.y - y * b.x;}↵
int len() {return x * x + y * y;}↵
};↵
pt a[N];↵
bool cmp(pt a, pt b) {↵
int sign = a % b;↵
if (sign > 0) return 1;↵
if (sign < 0) return 0;↵
return a.len() < b.len() ? 1 : 0;↵
}↵
vector<pt> hull;↵
int mx[N];↵
ld find(int lx, int ly, int rx, int ry, int px, int py) {↵
ld k = (ld)py / px;↵
return (lx * ry - ly * rx) / (k * (lx - rx) + ry - ly);↵
}↵
ld findgood(ld lx, ld ly, ld rx, ld ry, ld px, ld py) {↵
ld l = 0, r = 1e9;↵
for (int o = 0; o < 200; o++) {↵
ld mid = (l + r) / 2;↵
if ((lx - px / mid) * (ry - py / mid) - (ly - py / mid) * (rx - px / mid) >= 0) r = mid;↵
else l = mid;↵
}↵
return px / l;↵
}↵
signed main() {↵
cin.tie(0); ios_base::sync_with_stdio(0);↵
cout.precision(20);↵
cin >> n;↵
int longest = 0;↵
for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y, longest = max(longest, a[i].y);↵
sort(a, a + n, cmp);↵
hull.pb({0, 0});↵
hull.pb(a[0]);↵
for (int i = 1; i < n; i++) {↵
while (hull.size() >= 2 && (a[i] - hull[hull.size() - 2]) % (hull.back() - hull[hull.size() - 2]) >= 0) hull.pop_back();↵
hull.pb(a[i]);↵
}↵
mx[hull.size()] = 0;↵
for (int i = hull.size() - 1; i > 0; i--) {↵
mx[i] = max(mx[i + 1], hull[i].y);↵
}↵
cin >> q;↵
for (int o = 0; o < q; o++) {↵
pt P;↵
cin >> P.x >> P.y;↵
if (P % hull[1] >= 0 && 1) {↵
cout << (long double)P.y / longest << "\n";↵
continue;↵
}↵
if (P % hull.back() < 0 && 1) {↵
cout << "-1\n";↵
continue;↵
}↵
int l = 1, r = hull.size() - 1;↵
while (r - l > 1) {↵
int mid = l + r >> 1;↵
pt current = hull[mid];↵
if (current % P >= 0) l = mid;↵
else r = mid;↵
}↵
ld X = find(hull[l].x, hull[l].y, hull[r].x, hull[r].y, P.x, P.y);↵
cout << (long double)min(P.x / X, P.y / (ld)mx[r]) << "\n";↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
Can anybody explain what actually happened? How can formula be less precise than binary search
↵
Кто-нибудь может объяснить, что за чертовщина тут произошла? Как формульное решение может быть менее точным, чем бинпоиск?
