沫沫最近在玩一个二维的射箭游戏，如下图 1 所示，这个游戏中的 x 轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。

沫沫控制一个位于(0,0)的弓箭手，可以朝 0 至 90度中的任意角度（不包括 0度和 90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些 只有端点被射中的靶子。

这个游戏有多种模式，其中沫沫最喜欢的是闯关模式。

在闯关模式中，第一关只有一个靶 子，射中这个靶子即可进入第二关，这时在第一关的基础上会出现另外一个靶子，若能够一箭 双雕射中这两个靶子便可进入第三关，这时会出现第三个靶子。依此类推，每过一关都会新出 现一个靶子，在第 K 关必须一箭射中前 K 关出现的所有 K 个靶子才能进入第 K+1 关，否则游戏 结束。

沫沫花了很多时间在这个游戏上，却最多只能玩到第七关”七星连珠“，这让她非常困惑。 于是她设法获得了每一关出现的靶子的位置，想让你告诉她，最多能通过多少关

前排先提醒一下，做这道题就是在作死。

二分答案，然后就能够知道要选多少竖线，再判断是否存在二次函数穿过所有竖线即可。

二次函数判断与一堆竖线的交点？枚举两个点构成二次函数再判断？显然TLE。

考虑y=ax^2+bx，如果我们考虑判断是否有合法的a和b的话能不能更好写。

于是我们有y1/x<=ax+b<=y2/x，于是有：

-xa+y1/x<=b;

-xa+y2/x>=b;

很像线性规划，围成了一块面积。

那我们把所有这样的式子杂在一起求下半平面交就好了！

但是显然a<0,b>0，那么我们除了加外边框之外还要再加两条边。

另外如果可行域是一个点或一个线段也是可以的，为了避免误判需要将靶子上下扩大一点。

另外本题严重卡精度，开小了会WA，开大了会TLE。

我从未见过有如此卡爆精度之题！

你们为什么卡精度这么熟练，你们精度卡了多少遍！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef long double dl;const dl eps=1e-15;const dl INF=1e10;const int N=100020;struct point{dl x,y;};struct line{    point a,b;    dl angle;int id;    line(){}    line(dl x1,dl y1,dl x2,dl y2){    a.x=x1;a.y=y1;b.x=x2;b.y=y2;    angle=atan2(b.y-a.y,b.x-a.x);    }}e[N*2],t[N*2],q[N*2];int n,m;inline point getmag(point a,point b){    point s;    s.x=b.x-a.x;s.y=b.y-a.y;    return s;}inline dl multiX(point a,point b){    return a.x*b.y-b.x*a.y;}inline bool cmp(line a,line b){    if(fabs(a.angle-b.angle)
          
           t[cnt].angle))t[++cnt]=e[i]; } q[++r]=t[1];q[++r]=t[2]; for(int i=3;i<=cnt;i++){ while(l
           
            2;}int main(){ scanf("%d",&n); e[++m]=line(0,0,0,1),e[m].id=0; e[++m]=line(0,0,1,0),e[m].id=0; e[++m]=line(INF,INF,-INF,INF),e[m].id=0; e[++m]=line(-INF,INF,-INF,-INF),e[m].id=0; for(int i=1;i<=n;i++){ dl a,y1,y2; scanf("%Lf%Lf%Lf",&a,&y1,&y2);y1-=eps;y2+=eps; dl b=y1/a,c=y2/a; e[++m]=line(0,b,1,b-a),e[m].id=i; e[++m]=line(1,c-a,0,c),e[m].id=i; } sort(e+1,e+m+1,cmp); int l=1,r=n; while(l
            
             >1; if(pan(mid))l=mid; else r=mid-1; } printf("%d\n",l); return 0;}
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客： +

+++++++++++++++++++++++++++++++++++++++++++