- 设抛物线方程\(y = ax^2 + bx\), 那么对于一个靶子\((x_i,y_{down},y_{up})\)我们需要满足的条件就是
- \(\frac{y_{down}}{x_i} \leq ax_i + b \leq \frac{y_{up}}{x_i}\), 实际上可以看做二维平面上的一个半平面，
- 然后我们二分能打到的最远距离， 我们只需要求出这些半平面是否有交就好了
- 当然我们要把ab的合法范围勾选出来， 满足， a < 0, b > 0
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<iostream>
#define ll long long
#define double long double
#define M 600010
#define mmp make_pair
const double inf = pow(2, 60), eps = 1e-12;
using namespace std;
int read() {
int nm = 0, f = 1;
char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
return nm * f;
}
struct Vec {
double x, y;
Vec () {}
Vec(double a, double b) {
x = a, y = b;
}
Vec operator + (Vec b) {
return Vec(x + b.x, y + b.y);
}
Vec operator - (Vec b) {
return Vec(x - b.x, y - b.y);
}
Vec operator *(double a) {
return Vec(x * a, y * a);
}
double operator ^ (Vec a) {
return x * a.y - y * a.x;
}
} k[M];
struct Line {
Vec p, v;
double k;
int id;
Line() {}
Line(Vec a, Vec b, int c) {
p = a, v = b - a, k = atan2(v.y, v.x), id = c;
}
bool operator < (const Line &b) const
{
return this->k < b.k;
}
bool right(Vec a) {
return (v ^ (a - p)) < -eps;
}
friend Vec cross(Line a, Line b) {
return a.p + a.v * ((b.v ^ (b.p - a.p)) / (b.v ^ a.v));
}
} a[M], q[M];
int tp = 0, n;
bool check(int mid) {
int h = 0, t = 0, i = 1;
while(a[i].id > mid) i++;
for(q[0] = a[i++]; i <= tp; i++)
{
if(a[i].id > mid) continue;
while(h < t && a[i].right(k[t - 1])) --t;
while(h < t && a[i].right(k[h]))h++;
if(a[i].k != q[t].k) q[++t] = a[i];
else if(a[i].right(q[t].p)) q[t] = a[i];
if(h < t) k[t - 1] = cross(q[t - 1], q[t]);
}
while(h < t && q[h].right(k[t - 1])) --t;
return t - h > 1;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
double x = read(), yd = read(), yp = read();
a[++tp] = Line(Vec(0, yd / x), Vec(1, yd / x - x), i);
a[++tp] = Line(Vec(1, yp / x - x), Vec(0, yp / x), i);
}
a[++tp] = Line(Vec(-inf, eps), Vec(-eps, eps), 0);
a[++tp] = Line(Vec(-eps, eps), Vec(-eps, inf), 0);
a[++tp] = Line(Vec(-eps, inf), Vec(-inf, inf), 0);
a[++tp] = Line(Vec(-inf, inf), Vec(-inf, eps), 0);
sort(a + 1, a + tp + 1);
int l = 1, r = n;
while(l + 1 < r) {
int mid = (l + r) >> 1;
if(check(mid)) l = mid;
else r = mid;
}
printf("%d\n", check(r) ? r : l);
return 0;
}