显然我们可以二分答案。
然后。
我们设抛物线方程f(x)=ax^2+bx;
对于每一个限制，要求ly<=f(x)<=ry
我们把x,y代入（看为已知量）则方程变为 ly<=x^2*a+x*b<=ry
只有a,b是未知量，以a,b为轴建系，我们可以发现每个限制即是一半平面，直接做半平面交判定是否可行即可
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; struct point{ double x,y; point(double _x=0,double _y=0){ x=_x;y=_y; } }; struct line{ point p,v; int k,id; }; point operator +(point a,point b){return point(a.x+b.x,a.y+b.y);} point operator -(point a,point b){return point(a.x-b.x,a.y-b.y);} point operator *(point a,double b){return point(a.x*b,a.y*b);} double operator ^(point a,point b){return a.x*b.y-a.y*b.x;} point ict(line a,line b){return b.p+b.v*((a.v^(a.p-b.p))/(a.v^b.v));} double eps=1e-12; line li[300011],nw[300011]; point cro[300011]; int que[300011]; int n,i,l,r,mid,tot,ts; struct limit{ double x,ly,ry; }a[100011]; void newline(double A,double B,double C) { double sx,sy,tx,ty; sx=1;tx=5; if(B<0)swap(sx,tx); sy=(sx*-A-C)/B;ty=(tx*-A-C)/B; ts++; nw[ts].p=point(sx,sy);nw[ts].v=point(tx-sx,ty-sy); if(nw[ts].v.y>eps||(fabs(nw[ts].v.y)<eps&&nw[ts].v.x>eps))nw[ts].k=1; else nw[ts].k=0; } bool cmp(line a,line b) { if(a.k!=b.k)return a.k>b.k; else return (a.v^b.v)>eps; } bool f(line a,point x) { return (a.v^(x-a.p))<-eps; } bool check(int x) { int i,st,ed; tot=0; for(i=1;i<=ts;i++)if(nw[i].id<=x)li[++tot]=nw[i]; que[1]=1; st=ed=1; for(i=2;i<=tot;i++){ while(st<ed&&f(li[i],cro[ed-1]))ed--; while(st<ed&&f(li[i],cro[st]))st++; if(fabs((li[i].v^li[que[ed]].v))<eps){ if(f(li[i],li[que[ed]].p))que[ed]=i; } else que[++ed]=i; if(st<ed)cro[ed-1]=ict(li[que[ed-1]],li[que[ed]]); } while(st<ed&&f(li[que[st]],cro[ed-1]))ed--; while(st<ed&&f(li[que[ed]],cro[st]))st++; return st+1<ed; } int main() { scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%lf%lf%lf",&a[i].x,&a[i].ly,&a[i].ry); newline(a[i].x*a[i].x,a[i].x,-a[i].ly); nw[ts].id=i; newline(-a[i].x*a[i].x,-a[i].x,a[i].ry); nw[ts].id=i; } nw[++ts].p=point(-1e9,-1e9);nw[ts].v=point(1,0);nw[ts].k=1; nw[++ts].p=point(1e9,-1e9);nw[ts].v=point(0,1);nw[ts].k=1; nw[++ts].p=point(1e9,1e9);nw[ts].v=point(-1,0);nw[ts].k=0; nw[++ts].p=point(-1e9,1e9);nw[ts].v=point(0,-1);nw[ts].k=0; sort(nw+1,nw+1+ts,cmp); l=2; r=n; while(l<=r){ mid=(l+r)/2; if(check(mid))l=mid+1; else r=mid-1; } printf("%d ",r); }