传送门
黄学长的代码好清楚啊……大概搞明白半平面交是个什么玩意儿了……
设抛物线
\[y=ax^2+bx\]
则
\[y1<=ax1^2+bx1<=y2\]
\[ax1^2+bx1>=y1\]
\[bx1>=y1-ax1^2\]
\[b>=y1/x1-ax1\]
然后就可以转化为一个关于\(a,b\)的不等式了……那么就二分答案，用半平面交判断又没有解就行了
//minamoto
#include<bits/stdc++.h>
#define double long double
#define linf 1e15
#define fp(i,a,b) for(register int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(register int i=a,I=b-1;i>I;--i)
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){int res,f=1;char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f;
}
const int N=2e5+5;
struct node{double x,y;};int n,m,ans=0;
struct line{node a,b;int id;double slop;}q[N],a[N],l[N];
inline node operator -(node a,node b){return {a.x-b.x,a.y-b.y};}
inline double operator *(node a,node b){return a.x*b.y-a.y*b.x;}
double cal(double a,double b,int x){return b/a-a*x;}
inline bool operator <(line a,line b){return a.slop==b.slop?(a.b-a.a)*(b.a-a.a)<0:a.slop<b.slop;}
node inter(line a,line b){double k1,k2,t;k1=(b.b-a.a)*(a.b-a.a);k2=(a.b-a.a)*(b.a-a.a);t=k2/(k1+k2);return {b.a.x+t*(b.b.x-b.a.x),b.a.y+t*(b.b.y-b.a.y)};
}
inline bool jd(line a,line b,line c){node p=inter(a,b);return (p-c.a)*(c.b-c.a)>0;}
bool check(int x){int tot=0;fp(i,1,m)if(l[i].id<=x&&l[i].slop!=a[tot].slop)a[++tot]=l[i];int h=1,t=0;q[++t]=a[1],q[++t]=a[2];fp(i,3,tot){while(h<t&&jd(q[t-1],q[t],a[i]))--t;while(h<t&&jd(q[h+1],q[h],a[i]))++h;q[++t]=a[i];}while(h<t&&jd(q[t-1],q[t],q[h]))--t;while(h<t&&jd(q[h+1],q[h],q[t]))++h;return t>=h+2;
}
int main(){
// freopen("testdata.in","r",stdin);l[++m].a={-linf,-linf};l[m].b={linf,-linf};l[++m].a={linf,-linf};l[m].b={linf,linf};l[++m].a={linf,linf};l[m].b={-linf,linf};l[++m].a={-linf,linf};l[m].b={-linf,-linf};n=read();fp(i,1,n){double x=read(),ya=read(),yb=read();l[++m].a.x=-1,l[m].a.y=cal(x,ya,-1);l[m].b.x=1,l[m].b.y=cal(x,ya,1);l[++m].a.x=1,l[m].a.y=cal(x,yb,1);l[m].b.x=-1,l[m].b.y=cal(x,yb,-1);l[m].id=l[m-1].id=i;}fp(i,1,m)l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);sort(l+1,l+1+m);int l=1,r=n,mid;while(l<=r){mid=(l+r)>>1;check(mid)?(ans=mid,l=mid+1):(r=mid-1);}printf("%d\n",ans);return 0;
}