[HNOI2012]射箭

题目

wdnmd这精度卡死我了

不难发现答案是存在单调性的，于是我们二分就好了；现在要做的就是给定一些竖直线段，问是否存在一条标准抛物线经过所有线段

对于一条线段\((x_i,l_i,r_i)\)，如果\(f(x)=ax^2+bx\)经过它的话需要满足\(l_i\leq ax_i^2+bx_i\leq r_i\)

也就是说\(ax_i^2+bx_i-l_i\geq 0,ax_i^2+bx_i-r_i\leq 0\)

这里的\(x_i,l_i,r_i\)都是常数啊，于是我们考虑把\(a,b\)看成平面上的点，于是这又变成了直线的解析式了，我们还是半平面交即可。

注意到这是一条标准的抛物线，于是需要满足\(a<0,b>0\)，于是我们在加两条直线将\((a,b)\)限制在第二象限内就好了

提前排好序，二分的时候直接用就能做到\(O(n\log n)\)的复杂度了

之后大力卡卡精度就过了

代码

#include<bits/stdc++.h>
#define re register
#define double long double
const double eps=1e-15;
const double inf=1e18;
const int maxn=1e5+5;
int n,N,h,t,cnt,tot;
struct pt{double x,y;};
struct Line{pt s,t;double det;int id;}q[maxn<<1],L[maxn<<1],d[maxn<<1];
inline int dcmp(double a,double b) {return a+eps>b&&a-eps<b;}
const pt operator^(double t,const pt &A) {return (pt){t*A.x,t*A.y};}
inline double operator*(const pt &A,const pt &B) {return A.x*B.y-A.y*B.x;}
inline pt operator+(const pt &A,const pt &B) {return (pt){A.x+B.x,A.y+B.y};}
inline pt operator-(const pt &A,const pt &B) {return (pt){A.x-B.x,A.y-B.y};}
inline int OnRight(const pt &c,const Line &A) {return (A.t-c)*(A.s-c)>0;}
inline pt sec(const Line &A,const Line &B) {
    pt v1=A.t-A.s,v2=B.t-B.s,v3=A.s-B.s;
    double t=(v3*v2)/(v2*v1);
    return A.s+(t^v1);
}
inline int cmp(const Line &A,const Line &B) {
    return dcmp(A.det,B.det)?OnRight(A.s,B):(A.det<B.det);
}
inline int half(int mid) {
    cnt=0,tot=1;h=1,t=0;
    for(re int i=1;i<=N;i++)if(L[i].id<=mid)d[++cnt]=L[i];
    for(re int i=2;i<=cnt;i++) {
        if(!dcmp(d[i-1].det,d[i].det)) ++tot;
        d[tot]=d[i];
    }
    for(re int i=1;i<=tot;i++) {
        while(h<t&&OnRight(sec(q[t],q[t-1]),d[i])) --t;
        while(h<t&&OnRight(sec(q[h],q[h+1]),d[i])) ++h;
        q[++t]=d[i];
    }
    while(h<t&&OnRight(sec(q[t],q[t-1]),q[h])) --t;
    while(h<t&&OnRight(sec(q[h],q[h+1]),q[t])) ++h;
    return (t-h>1);
}
int main() {
    scanf("%d",&n);double c,sq,l,r;
    for(re int i=1;i<=n;i++) {
        scanf("%Lf%Lf%Lf",&c,&l,&r);sq=c*c;
        L[++N].id=i;L[N].s=(pt){-1,(l+sq)/c},L[N].t=(pt){1,(l-sq)/c};
        L[++N].id=i;L[N].s=(pt){1,(r-sq)/c};L[N].t=(pt){-1,(r+sq)/c};
    }
    L[++N].s=(pt){-eps,eps},L[N].t=(pt){-eps,inf};
    L[++N].s=(pt){-inf,eps},L[N].t=(pt){-eps,eps};
    for(re int i=1;i<=N;i++)L[i].det=atan2((L[i].t-L[i].s).y,(L[i].t-L[i].s).x);
    std::sort(L+1,L+N+1,cmp);
    int L=1,R=n,nw=0;
    while(L<=R) {
        int mid=L+R>>1;
        if(half(mid)) L=mid+1,nw=mid;else R=mid-1;
    }
    printf("%d\n",nw);return 0;
}