bzoj 2732: [HNOI2012]射箭半平面交

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2732

高中的线性规划知识

一个线段可以转变为两个半平面，然后二分答案，跑半平面交

注意精度问题，及其的恶心， $ long double $ 和 $ 1e-18 $ 的 $eps$ ……

#include<bits/stdc++.h>

#define db long double
#define Vector point
#define maxn 100010
#define eps 1e-18
#define inf 1e10

using namespace std;

inline int rd(){
    int x=0,y=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*y;
}

struct point{
    db x,y;
    point(db xx=0,db yy=0){x=xx,y=yy;}
    friend Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
    friend Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}
    friend Vector operator * (Vector A,db B){return Vector(A.x*B,A.y*B);}
    friend Vector operator / (Vector A,db B){return Vector(A.x/B,A.y/B);}
}p[maxn*2];

struct line{
    int id;
    point p;
    Vector v;
    db ang;
    line(){}
    line(point A,Vector B,int C){
        p=A;
        v=B;
        ang=atan2(B.y,B.x);
        id=C;
    }
    friend bool operator < (line A,line B){
        return A.ang<B.ang;
    }
}L[maxn*2],q[maxn*2];

inline db cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}

inline bool OnLeft(line A,point p){
    return cross(A.v,p-A.p)>-eps;
}

inline point GetPoint(line A,line B){
    Vector v=A.p-B.p;
    db tmp=cross(B.v,v)/cross(A.v,B.v);
    return A.p+A.v*tmp;
}

int n,tot;

inline void init(){
    n=rd();
    for(int i=1; i<=n; i++){
        db x=rd(),y=rd(),yy=rd();
        y-=eps;
        yy+=eps;
        point p1=point(0,y/x),p2=point(1,(y-x*x)/x);
        L[++tot]=line(p1,p2-p1,i);
        p1=point(0,yy/x),p2=point(1,(yy-x*x)/x);
        L[++tot]=line(p2,p1-p2,i);
    }
    L[++tot]=line(point(-eps,0),point(0,1),0);
    L[++tot]=line(point(0,inf),point(-1,0),0);
    L[++tot]=line(point(-inf,0),point(0,-1),0);
    L[++tot]=line(point(0,eps),point(1,0),0);
    sort(L+1,L+tot+1);
}

inline bool hpi(int mid){
    int now=1;
    int head=1,tail=0;
    while(L[now].id>mid)now++;
    q[++tail]=L[now];
    for(int i=now+1; i<=tot; i++){
        if(L[i].id>mid)continue;
        while(head<tail && !OnLeft(L[i],p[tail-1]))tail--;
        while(head<tail && !OnLeft(L[i],p[head]))head++;
        q[++tail]=L[i];
        if(fabs(cross(q[tail].v,q[tail-1].v))<eps){
            tail--;
            if(OnLeft(q[tail],L[i].p))q[tail]=L[i];
        }
        if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);
    }
    while(head<tail && !OnLeft(q[head],p[tail-1]))tail--;
    while(head<tail && !OnLeft(q[tail-1],p[head]))head++;
    p[tail]=GetPoint(q[tail],q[head]);
    return tail-head>=2;
}

inline void work(){
    int l=2,r=n,ans=1;
    while(l<=r){
        int mid=(l+r)/2;
        if(hpi(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d\n",ans);
}

int main(){
    init();
    work();
    
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include<bits/stdc++.h>

#define db long double

#define Vector point

#define maxn 100010

#define eps 1e-18

#define inf 1e10

using namespace std;

inline int rd(){

int x=0,y=1;char c=getchar();

while(!isdigit(c)){if(c=='-')y=-y;c=getchar();}

while(isdigit(c))x=x*10+c-'0',c=getchar();

return x*y;

}

struct point{

db x,y;

point(db xx=0,db yy=0){x=xx,y=yy;}

friend Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

friend Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}

friend Vector operator * (Vector A,db B){return Vector(A.x*B,A.y*B);}

friend Vector operator / (Vector A,db B){return Vector(A.x/B,A.y/B);}

}p[maxn*2];

struct line{

int id;

point p;

Vector v;

db ang;

line(){}

line(point A,Vector B,int C){

p=A;

v=B;

ang=atan2(B.y,B.x);

id=C;

}

friend bool operator < (line A,line B){

return A.ang<B.ang;

}

}L[maxn*2],q[maxn*2];

inline db cross(Vector A,Vector B){

return A.x*B.y-A.y*B.x;

}

inline bool OnLeft(line A,point p){

return cross(A.v,p-A.p)>-eps;

}

inline point GetPoint(line A,line B){

Vector v=A.p-B.p;

db tmp=cross(B.v,v)/cross(A.v,B.v);

return A.p+A.v*tmp;

}

int n,tot;

inline void init(){

n=rd();

for(int i=1; i<=n; i++){

db x=rd(),y=rd(),yy=rd();

y-=eps;

yy+=eps;

point p1=point(0,y/x),p2=point(1,(y-x*x)/x);

L[++tot]=line(p1,p2-p1,i);

p1=point(0,yy/x),p2=point(1,(yy-x*x)/x);

L[++tot]=line(p2,p1-p2,i);

}

L[++tot]=line(point(-eps,0),point(0,1),0);

L[++tot]=line(point(0,inf),point(-1,0),0);

L[++tot]=line(point(-inf,0),point(0,-1),0);

L[++tot]=line(point(0,eps),point(1,0),0);

sort(L+1,L+tot+1);

}

inline bool hpi(int mid){

int now=1;

int head=1,tail=0;

while(L[now].id>mid)now++;

q[++tail]=L[now];

for(int i=now+1; i<=tot; i++){

if(L[i].id>mid)continue;

while(head<tail && !OnLeft(L[i],p[tail-1]))tail--;

while(head<tail && !OnLeft(L[i],p[head]))head++;

q[++tail]=L[i];

if(fabs(cross(q[tail].v,q[tail-1].v))<eps){

tail--;

if(OnLeft(q[tail],L[i].p))q[tail]=L[i];

}

if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]);

}

while(head<tail && !OnLeft(q[head],p[tail-1]))tail--;

while(head<tail && !OnLeft(q[tail-1],p[head]))head++;

p[tail]=GetPoint(q[tail],q[head]);

return tail-head>=2;

}

inline void work(){

int l=2,r=n,ans=1;

while(l<=r){

int mid=(l+r)/2;

if(hpi(mid))l=mid+1,ans=mid;

else r=mid-1;

}

printf("%d\n",ans);

}

int main(){

init();

work();

return 0;

}

everlasting

bzoj 2732: [HNOI2012]射箭半平面交

赞过：

相关

发表评论取消回复

共享此文章：

赞过：

相关

发表评论 取消回复

发表评论取消回复