首页 > 代码库 > BZOJ 2732: [HNOI2012]射箭

BZOJ 2732: [HNOI2012]射箭

Description

问一条过原点的抛物线最多能连续穿过几条线段.\(n \leqslant 10^5\)

Solution

二分+计算几何半平面交
过一条线段可以变成两个不等式,都写成\(ax+by+c\geqslant 0\)的形式.
这题蜜汁精度..

Code

/**************************************************************    Problem: 2732    User: BeiYu    Language: C++    Result: Accepted    Time:5540 ms    Memory:36028 kb****************************************************************/ #include <bits/stdc++.h>using namespace std;  namespace CG {    typedef long double LD;          const LD Pi = M_PI;    const LD PI = 2 * acos(0.0);    const LD eps = 1e-18;    const LD oo = 1e15;    #define sqr(x) ((x)*(x))          int dcmp(LD x) { return fabs(x)<=eps?0:(x<0?-1:1); }          struct Point {        LD x,y;        Point(LD _x=0,LD _y=0) :x(_x),y(_y) {}        void out() { cout<<"("<<x<<","<<y<<")"; }    };    typedef Point Vector;          int cmpx(const Point &a,const Point &b) { return dcmp(a.x-b.x)==0?a.y<b.y:a.x<b.x; }          Vector operator + (const Vector &a,const Vector &b) { return Vector(a.x+b.x,a.y+b.y); }    Vector operator - (const Vector &a,const Vector &b) { return Vector(a.x-b.x,a.y-b.y); }    Vector operator * (const Vector &a,LD b) { return Vector(a.x*b,a.y*b); }    Vector operator / (const Vector &a,LD b) { return Vector(a.x/b,a.y/b); }    bool operator == (const Point &a,const Point &b) { return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; }          LD Dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; }    LD Cross(Vector a,Vector b) { return a.x*b.y-b.x*a.y; }    Vector Rot(Vector a,LD rd) { return Vector(a.x*cos(rd)-a.y*sin(rd),a.x*sin(rd)+a.y*cos(rd)); }    LD get_l(Vector a) { return sqrt(Dot(a,a)); }    LD get_d(Point a,Point b) { return sqrt(Dot(a-b,a-b)); }    LD get_a(Vector a) { return atan2(a.y,a.x); }    LD get_a(Vector a,Vector b) { return acos(Dot(a,b)/get_l(a)/get_l(b)); }     LD get_s(Point a,Point b,Point c) { return Cross(b-a,c-a)/2.0; }          struct Line {        Point p;        Vector v;        LD ang;        Line(Point _p=Point(),Vector _v=Vector()):p(_p),v(_v) { ang=get_a(v); }         LD get_l() { return sqrt(Dot(v,v)); }         Point get_p(LD t) { return p+v*t; }        Point get_s() { return p; }        Point get_t() { return p+v; }        int chkleft(Point P) { return dcmp(Cross(v,P-p))>0; }    };    int cmpa(const Line &a,const Line &b) { return dcmp(a.ang-b.ang)==-1; }    Point get_l_l(Line a,Line b) {        Vector u=a.p-b.p;        LD t=Cross(b.v,u)/Cross(a.v,b.v);        return a.get_p(t);    }    typedef Line Hp;    int get_h_h(vector<Hp> &hs,vector<Point> &pt) {        sort(hs.begin(),hs.end(),cmpa);/*      for(int i=0;i<(int)hs.size();i++) {            hs[i].p.out();cout<<" ";hs[i].v.out();cout<<" "<<hs[i].ang<<endl;        }*/        vector<Point> p(hs.size());        vector<Hp> q(hs.size());        int h,t;        q[h=t=0]=hs[0];/*      for(int i=0;i<(int)hs.size();i++) {            for(int j=0;j<(int)hs.size();j++)                 get_l_l(hs[i],hs[j]).out(),cout<<" ";                cout<<endl;        }*/        for(int i=1;i<(int)hs.size();i++) {            while(h<t && !hs[i].chkleft(p[t-1])) t--;            while(h<t && !hs[i].chkleft(p[h])) h++;            q[++t]=hs[i];            if(fabs(Cross(q[t].v,q[t-1].v))<eps) {                t--;                if(q[t].chkleft(hs[i].p)) q[t]=hs[i];            }            if(h<t) p[t-1]=get_l_l(q[t-1],q[t]);        }        while(h<t && !q[h].chkleft(p[t-1])) t--;//      cout<<t-h+1<<endl;        p[t]=get_l_l(q[h],q[t]);//      for(int i=h;i<=t;i++) pt.push_back(p[i]);        return t-h+1;    }         struct Circle {        Point c;        LD r;        Point get_p(LD t) { return c+Point(cos(t)*r,sin(t)*r); }        LD get_rd(Point a,Point b) { return get_a(a-c,b-c); }        LD get_l(LD rd) { return r*rd; }     };          int get_c_l(Line L,Circle C,vector<Point> &res) {        LD a=L.v.x,b=L.p.x-C.c.x,c=L.v.y,d=L.p.y-C.c.y;        LD e=sqr(a)+sqr(c),f=2.0*(a*b+c*d),g=sqr(b)+sqr(d)-sqr(C.r);        LD dt=f*f-4*e*g;        if(dcmp(dt)<0) return 0;        if(dcmp(dt)==0) return res.push_back(L.get_p(-f/(2.0*e))),1;        LD x1=(-f-sqrt(dt))/(2.0*e),x2=(-f+sqrt(dt))/(2.0*e);        if(x1>x2) swap(x1,x2);        res.push_back(L.get_p(x1)),res.push_back(L.get_p(x2));return 2;    }    int get_c_c(Circle A,Circle B,vector<Point> &res) {        LD d=get_l(A.c-B.c);        if(dcmp(d)==0) return dcmp(A.r-B.r)==0?-1:0;        if(dcmp(A.r+B.r-d)<0) return 0;        if(dcmp(fabs(A.r-B.r)-d)>0) return 0;                  LD a=get_a(B.c-A.c);        LD rd=acos((sqr(A.r)+sqr(d)-sqr(B.r))/(2.0*A.r*d));                  Point p1,p2;        p1=A.get_p(a+rd),p2=A.get_p(a-rd);                  res.push_back(p1);        if(p1==p2) return 1;        res.push_back(p2);        return 2;    }          /*---io---*/      ostream & operator << (ostream &os,const Point &p) { os<<p.x<<" "<<p.y;return os; }    istream & operator >> (istream &is,Point &p) { is>>p.x>>p.y;return is; }    ostream & operator << (ostream &os,const Circle &C) { os<<C.c<<" "<<C.r;return os; }    istream & operator >> (istream &is,Circle &C) { is>>C.c>>C.r;return is; }};  using namespace CG; const int N = 2e5+500; int n;LD xx[N],sy[N],ty[N];vector<Line> ls;vector<Point> pt; int chk(int x) {    ls.clear();/*  ls.push_back(Line(Point(0,0),Point(oo,0)));    ls.push_back(Line(Point(-1e-13,0),Point(0,oo)));    ls.push_back(Line(Point(0,oo),Point(-oo,0)));    ls.push_back(Line(Point(-oo,0),Point(0,-oo)));*/    ls.push_back(Line(Point(0,0),Point(0,oo)));    ls.push_back(Line(Point(0,oo),Point(-oo,0)));    ls.push_back(Line(Point(-oo,oo),Point(0,-oo)));    ls.push_back(Line(Point(-oo,0),Point(oo,0)));    for(int i=1;i<=x;i++) {        LD a=sqr(xx[i]),b=xx[i],c1=sy[i],c2=ty[i];        ls.push_back(Line(Point(0,c2/b),Point(-1e3,1e3*a/b)));        ls.push_back(Line(Point(0,c1/b),Point(1e3,-1e3*a/b)));    }return get_h_h(ls,pt)>=3;}int main() {    scanf("%d",&n);    for(int i=1;i<=n;i++) {        int a,b,c;        scanf("%d%d%d",&a,&b,&c);        xx[i]=a,sy[i]=b-eps,ty[i]=c+eps;    }//  for(int i=1;i<=n;i++) cout<<chk(i)<<endl;    int l=0,r=n,md;    for(;l<=r;) {        md=(l+r)>>1;        if(chk(md)) l=md+1;        else r=md-1;    }printf("%d\n",r);    return 0;}

  

BZOJ 2732: [HNOI2012]射箭