Description：

平面上有 $n$ 个竖直的线段，每次可以从原点发射一条抛物线，问最多能从第一个开始连续穿过几条线段。

$1\leqslant n\leqslant 10^5$

Solution：

设抛物线的方程为 $y=ax^2+bx$ ，那么我们可以二分最后的答案，然后判断是否存在一个抛物线能穿过所有线段，发现每一个线段都是两个类似 $ax_0^2+bx_0\leqslant/\geqslant y_0$ 的限制，如果我们把 $a$ 看成 $x$ ， $b$ 看成 $y$ ，那么会发现这个限制就是一个半平面，于是做半平面交判断是否有解即可。

Code：

好像卡精度， $60$ 调不出来了。。。

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

struct segment

{

    double x,y1,y2;

}s[MAXN];

struct point

{

    double x,y;

    point(double x_ = 0.0,double y_ = 0.0){x = x_;y = y_;}

}p[MAXN << 1];

typedef point vector;

vector operator + (vector a,vector b){return (vector){a.x + b.x,a.y + b.y};}

vector operator - (vector a,vector b){return (vector){a.x - b.x,a.y - b.y};}

vector operator * (vector a,double b){return (vector){a.x * b,a.y * b};}

double crossmul(vector a,vector b){return a.x * b.y - a.y * b.x;}

double angle(vector a){return atan2(a.y,a.x);}

#define eps 1e-10

bool equal(double a,double b){return (fabs(a - b) < eps);}

int sign(double k){return (equal(k,0.0) ? 0 : (k < 0 ? -1 : 1));}

struct plane

{

    point p;vector v;

    plane(){};

    plane(point p_,point v_){p = p_;v = v_;}

}pl[MAXN << 1],q[MAXN << 1];

int head,tail;

bool in(point p,plane k){return sign(crossmul(p - k.p,k.v)) >= 0;}

point intersection(plane a,plane b){return b.p + b.v * (crossmul(a.v,a.p - b.p) / crossmul(a.v,b.v));}

bool cmp(plane a,plane b){return angle(a.v) < angle(b.v);}

bool check(int k)

{

    if(k <= 1)return true;

    int n = 0;

    point a,b;

    for(int i = 1;i <= k;++i)

    {

        a = (point){100.0,-1.0 * s[i].x * 100 + s[i].y1 * 100 / s[i].x};

        b = (point){0.0,s[i].y1 * 100 / s[i].x};

        pl[++n] = (plane){a,b - a};

        a = (point){100.0,-1.0 * s[i].x * 100 + s[i].y2 * 100 / s[i].x};

        b = (point){0.0,s[i].y2 * 100 / s[i].x};

        pl[++n] = (plane){a,a - b};

    }

    sort(pl + 1,pl + 1 + n,cmp);

    int tot = 0;

    for(int i = 1;i <= n;++i)

    {

        if(tot == 0)pl[++tot] = pl[i];

        else if(!equal(angle(pl[tot].v),angle(pl[i].v)))pl[++tot] = pl[i];

        else if(!in(pl[tot].p,pl[i]))pl[tot] = pl[i];

    }

    n = tot;head = 1;tail = 2;

    q[1] = pl[1];q[2] = pl[2];

    for(int i = 3;i <= n;++i)

    {

        while(head < tail && !in(intersection(q[tail],q[tail - 1]),pl[i]))--tail;

        while(head < tail && !in(intersection(q[head],q[head + 1]),pl[i]))++head;

        if(head == tail && sign(crossmul(q[head].v,pl[i].v)) <= 0)return false;

        q[++tail] = pl[i];

    }

    while(head < tail && !in(intersection(q[tail],q[tail - 1]),q[head]))--tail;

    int m = tail - head + 1;

    for(int i = 1;i < m;++i)p[i] = intersection(q[head + i - 1],q[head + i]);

    p[0] = p[m] = intersection(q[head],q[tail]);

    double ans = 0;

    for(int i = 0;i < m;++i)ans = ans + crossmul(p[i],p[i + 1]);

    return sign(ans) > 0;

}

int main()

{

    scanf("%d",&n);

    for(int i = 1;i <= n;++i)scanf("%lf%lf%lf",&s[i].x,&s[i].y1,&s[i].y2);

    int l = 1,r = n,mid;

    while(l < r)

    {

        mid = ((l + r + 1) >> 1);

        if(check(mid))l = mid;

        else r = mid - 1;

    }

    cout << l << endl;

    return 0;

}