Description

沫沫最近在玩一个二维的射箭游戏，如下图1 所示，这个游戏中的x 轴在地面，第一象限

中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。

沫沫控制一个位于(0,0)的弓箭手，可以朝0 至90°中的任意角度（不包括0°和90°），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些只有端点被射中的靶子。这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。在闯关模式中，第一关只有一个靶子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出现一个靶子，在第K 关必须一箭射中前K 关出现的所有K 个靶子才能进入第K+1 关，否则游戏结束。

沫沫花了很多时间在这个游戏上，却最多只能玩到第七关“七星连珠”，这让她非常困惑。

于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关。

 

 

 

Input

输入第一行是一个正整数N，表示一共有N关。接下来有

N行，第i+1行是用空格隔开的三个正整数xi，yi1，yi2(yi1<yi2)，表示第i关出现的靶子的横坐标

是xi，纵坐标的范围是从yi1到yi2。

 

 

 

Output

输出仅包含一个整数，表示最多的通关数。

 

 

Sample Input

5 2 8 12 5 4 5 3 8 10 6 2 3 1 3 7

Sample Output

3

 

Data Constraint

 

 

Hint

 

【数据范围】

输入保证30%的数据满足N≤100，50%的数据满足N≤5000，100%的数据满足N≤100000且给

出的所有坐标不超过10^9。

【样例解释】

如图1所示，可以射中前三关的靶子。

 

显然我们可以二分答案。

然后。

我们设抛物线方程f(x)=ax^2+bx;

对于每一个限制，要求ly<=f(x)<=ry

我们把x,y代入（看为已知量）则方程变为 ly<=x^2*a+x*b<=ry

只有a,b是未知量，以a,b为轴建系，我们可以发现每个限制即是一半平面，直接做半平面交判定是否可行即可

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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].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