题意:给出n条y轴右侧的和y轴平行的线段,问用一条经过(0,0)开口向下且对称轴在y轴右侧的抛物线最多能贯穿多少条编号从1开始依次递增的线段.

分析:首先有单调性,考虑二分答案转化为判定问题,那么记抛物线为y=ax^2+bx(a<0,b>0),每个线段对应两个关于a和b的二元一次不等式,也就是两个半平面，我们对当前需要打穿的靶子找出半平面,用半平面交求出(a,b)的可行域判断是否非空即可.因为a<0,b>0所以还要加包围框.

然后…这数据好强….我WA了17次,好像不是最多的…最后面向数据debug了一波

1.可行域可以是一个点或一个线段,这时也是有解的.我把靶子向上下各延长一点,这样点和线段就变成了多边形

2.使用long double

3.eps需要不断的尝试,不同的代码可能需要不同的eps,我最后是1e-18过的

4.ax^2+bx必须满足a<0,b>0,需要在包围框中体现这个限制

5.a,b不能等于0,所以包围框的坐标不能放在0,需要把包围框稍微移动一点,比如从0挪到-1e-13

WA17次.....好像还不是最多的...

要了数据...一个是原数据,一个是加强的一些边界数据

http://files.cnblogs.com/files/liu-runda/%E5%8A%A0%E5%BC%BA%E7%9A%84%E6%95%B0%E6%8D%AE.zip 

http://files.cnblogs.com/files/liu-runda/%E9%83%A8%E5%88%86%E5%8E%9F%E6%95%B0%E6%8D%AE.rar 

#include
     
      #include
      
       #include
       
        using namespace std;const long double eps=1e-18;int cmp(long double x){
   return x<-eps?-1:x>eps;}const int maxn=300000;struct point{  long double x,y;  point(){}  point(long double a,long double b){x=a;y=b;}}p[maxn];point operator +(const point &A,const point &B){
   return point(A.x+B.x,A.y+B.y);}point operator -(const point &A,const point &B){
   return point(A.x-B.x,A.y-B.y);}long double cross(const point &A,const point &B){
   return A.x*B.y-A.y*B.x;}struct line{  point s,d;long double arg;line(){}  line(point S,point D){s=S;d=D;arg=atan2(d.y,d.x);}  bool operator <(const line &B)const{    return cmp(arg-B.arg)==-1;  }}L[maxn],q[maxn];long double x[maxn],Y1[maxn],Y2[maxn];int n,head,tail;point mult(long double t,point A){
   return point(A.x*t,A.y*t);}point intersect(line A,line B){  long double t=cross(B.d,A.s-B.s)/cross(A.d,B.d);  return A.s+mult(t,A.d);}bool toleft(line A,point B){  return cmp(cross(A.d,B-A.s))>0;}bool HPI(){  sort(L,L+n);  head=tail=0;q[tail++]=L[0];  for(int i=1;i
        
         =3;}bool check(int ans){  n=0;  L[n++]=line(point(0,0),point(1e15,0));L[n++]=line(point(-1e-13,0),point(0,1e15));  L[n++]=line(point(0,1e15),point(-1e15,0));L[n++]=line(point(-1e15,0),point(0,-1e15));//cha  long double a,b,c1,c2;  for(int i=1;i<=ans;++i){    a=x[i]*x[i];b=x[i];c1=Y1[i];c2=Y2[i];    L[n++]=line(point(0,c2/b),point(-1e3,1e3*a/b));L[n++]=line(point(0,c1/b),point(1e3,-1e3*a/b));  }  //  for(int i=0;i
         
          >1;    if(check(mid))l=mid+1;    else r=mid-1;  }  printf("%d\n",l-1);  return 0;}