首页 > 代码库 > bzoj 2732 [HNOI2012]射箭 半平面交（刘汝佳版不超时） + 整型二分处理

bzoj 2732 [HNOI2012]射箭 半平面交（刘汝佳版不超时） + 整型二分处理

2024-07-05 11:39:51   224人阅读

题目来源：

http://61.187.179.132/JudgeOnline/problem.php?id=2732

题意:   对于一个靶子， 得到两个不等式。 裸地半平面交 。 

分析：

用的 一般的 模板，总是TLE 。

改成了 刘汝佳 版本 ，依然超时， 所谓的常数太大？？？？ 

后来注意到 ： 当    判断两个向量平行且 同向 ，取左边的一个，不要用 叉积，用极角判断， 可行。

精度 开 1e -16 ， 卡精度严重。

注意：这里 也不需要用 friend 写， 也可以ac.

整型二分左闭右闭区间 ：

int Bin_search(){
    int  mid , Mid = 0 , l = 0 , r = n ;
    while(l <= r){
        mid = (r + l) >> 1 ;
        if(check(mid)){
            Mid = mid ;
            l = mid  + 1;
            }
        else r = mid - 1 ;
    }
    return  Mid ;
}

 

代码如下

:

const double EPS = 1e-16 ;
const int Max_N =  200010 ;
double add(double a, double b){
    return (fabs(a + b) < EPS * (fabs(a) + fabs(b)) ) ?  0 : (a + b );
}
struct Point {
    double x, y;
    Point(){}
    Point(double x, double y):x(x) , y(y){}
    friend Point operator - (const Point &b , const Point &a){
        return Point(add(b.x , -a.x) , add(b.y , -a.y)) ;
    }
    friend Point operator + (const Point &b , const Point &a){
        return Point(add(b.x , a.x) , add(b.y , a.y)) ;
    }
    friend Point operator * (const Point &a , double d){
        return Point(a.x * d , a.y * d) ;
    }
};
double Cross(const Point &a, const Point &b){return add(a.x * b.y , -a.y * b.x) ; }
struct Line{  //有向直线
    Point st, ed;
    double rad ;
    Line(){}
    Line(const Point &st, const Point &ed):st(st),ed(ed){ rad = atan2(ed.y - st.y , ed.x - st.x) ;}
    friend bool operator < (const Line &a , const Line &b){
        return a.rad - b.rad < - EPS ;
    }
};
bool onLeft(const Point &a ,const  Line &l){ //点a在直线向量的左边
    return Cross(a - l.st , l.ed - l.st) <= 0 ;
}
Point Crossnode(const Line &l , const Line &bl){ //两直线的交点
    double t =  Cross(l.ed - l.st , l.st - bl.st);
    double t1 = Cross(l.ed - l.st , bl.ed - bl.st) ;
    return bl.st + (bl.ed - bl.st)*(t / t1) ;
}
//用于计算的双端队列
Line deq[Max_N] ;
Point pt[Max_N] ;
bool halfPanelCross(Line line[] , int ln){
    int i;
    sort(line + 1, line  + ln + 1 ) ;
    int first = 1 , last = 1 ;
    deq[last] = line[1] ;
    for(i = 2 ; i <= ln  ; i++){
        while(first < last && !onLeft(pt[last - 1] , line[i])) last -- ;
        while(first < last && !onLeft(pt[first] , line[i] ) ) first ++ ;
        deq[++ last] = line[i] ;
        if(fabs(deq[last - 1].rad- line[i].rad) < EPS && onLeft(line[i].st , deq[--last]) )
            deq[last] = line[i] ;
        if(first < last) pt[last - 1] = Crossnode(deq[last] , deq[last - 1]) ;
    }
    while(first < last && !onLeft(pt[last - 1] , deq[first]) ) last -- ;
    return last - first > 1 ;
}
Line List[Max_N]  , tmp[Max_N];
int n;
bool check(int mid){
    for(int i = 1 ; i <= mid*2 ; i++)
        tmp[i] = List[i] ;
    return halfPanelCross(tmp , mid *2) ;
}
int Bin_search(){
    int  mid , Mid = 0 , l = 0 , r = n ;
    while(l <= r){
        mid = (r + l) >> 1 ;
        if(check(mid)){
            Mid = mid ;
            l = mid  + 1;
            }
        else r = mid - 1 ;
    }
    return  Mid ;
}
int main(){
    scanf("%d" , &n) ;
        int  i  ;
        double x, y1 ,y2 ;
        int ln = 0 ;
        for(i =1; i <= n ; i++){
            scanf("%lf%lf%lf" , &x , &y1 ,&y2) ;
            List[++ ln ] = Line(Point(0 , y1 / x) , Point(1 , y1 / x  - x ) ) ;
            List[++ ln ] = Line(Point(0 , y2 / x) , Point(-1 , y2 / x + x ) ) ;
        }
        printf("%d\n" ,Bin_search() ) ;
        return 0 ;
}

 

不加friend版本：

 double EPS = 1e-16 ;
 const int Max_N =  200010 ;
double add(double a, double b){
    return (fabs(a + b) < EPS * (fabs(a) + fabs(b)) ) ?  0 : (a + b );
}
struct Point {
    double x, y;
    Point(){}
    Point(double x, double y):x(x) , y(y){}
     Point operator - (  Point a){
        return Point(add(x , -a.x) , add(y , -a.y)) ;
    }
     Point operator + (  Point a){
        return Point(add(x , a.x) , add(y , a.y)) ;
    }
     Point operator * (  double d){
        return Point(x * d , y * d) ;
    }
};
double Cross( Point a,  Point b){return add(a.x * b.y , -a.y * b.x) ; }
struct Line{  //有向直线
    Point st, ed;
    double rad ;
    Line(){}
    Line( Point st,  Point ed):st(st),ed(ed){ rad = atan2(ed.y - st.y , ed.x - st.x) ;}
     bool operator < (  const  Line &b) const {
        return rad - b.rad < - EPS ;
    }
};
bool onRight(Point a ,Line l){ //点a在直线向量的右边
    return Cross(a - l.st , l.ed - l.st) > 0 ;
}
Point Crossnode( Line l ,  Line bl){ //两直线的交点
    double t =  Cross(l.ed - l.st , l.st - bl.st);
    double t1 = Cross(l.ed - l.st , bl.ed - bl.st) ;
    return bl.st + (bl.ed - bl.st)*(t / t1) ;
}
//用于计算的双端队列
Line deq[Max_N] ;
Point pt[Max_N] ;
Point poly[Max_N] ;
bool halfPanelCross(Line line[] , int ln){
    int i;
    sort(line + 1, line  + ln + 1 ) ;
    int first = 1 , last = 1 ;
    deq[last] = line[1] ;
    for(i = 2 ; i <= ln  ; i++){
        while(first < last && onRight(pt[last - 1] , line[i])) last -- ;
        while(first < last && onRight(pt[first] , line[i] ) ) first ++ ;
        deq[++ last] = line[i] ;
        //两向量平行且同向，取左边一个
        if(fabs(deq[last - 1].rad- line[i].rad) < EPS && !onRight(line[i].st , deq[--last]) )
            deq[last] = line[i] ;
        if(first < last) pt[last - 1] = Crossnode(deq[last] , deq[last - 1]) ;
    }
    while(first < last && onRight(pt[last - 1] , deq[first]) ) last -- ;
    return last - first > 1 ;
    if(last - first <= 1) return  0 ; // 空集
    pt[last] = Crossnode(deq[first] , deq[last]) ;
    // 从deq复制到输出中, 半平面交的凸多边形顶点
    int m = 0 ;
    for(i = first ; i <= last ; i++) poly[m++] = pt[i] ;
    return m ;

}

 


联系
我们