BZOJ-1038: [ZJOI2008]瞭望塔(半平面交)

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1038

裸裸的半平面交，WA了N次之后实在感叹O2下的精度实在DT，改成long double之后还发现居然还可以输出-0的额。。。唉~

代码：

#include <cstdio> 
#include <algorithm>
#include <cstring>
#include <cmath>
   
using namespace std ;
   
#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
#define maxn 1010
   
typedef long double ld ;
   
const ld esp = 0.0000001 ;
const ld inf = ld( 0x7fffffff ) * ld( 0x7fffffff ) ;
   
struct point {
       
    ld x , y ;
       
    void oper( ld _x , ld _y ) {
        x = _x , y = _y ;
    }
       
} p[ maxn ] , pos[ maxn ] ;
   
struct line {
       
    ld k , b ;
       
    void oper( point x , point y ) {
        k = ( x.y - y.y ) / ( x.x - y.x ) ;
        b = x.y - k * x.x ;
    }
       
    point cross( line l ) {
        point rec ;
        rec.x = - ( b - l.b ) / ( k - l.k ) ;
        rec.y = cal( rec.x ) ;
        return rec ;
    }
       
    ld cal( ld x ) {
        return k * x + b ;
    }
       
    bool operator < ( const line &a ) const {
        return k < a.k || ( k == a.k && b > a.b ) ;
    }
       
} li[ maxn ] , st[ maxn ] ;
   
int n , m = 0 , Top = 0 , M = 0 ;
    
ld calh( ld x , int left , int right , point *ret ) {
    if ( abs( ret[ left ].x - x ) < esp ) return ret[ left ].y ;
    if ( abs( ret[ right ].x - x ) < esp ) return ret[ right ].y ;
    while ( right - left > 1 ) {
        int mid = ( left + right ) >> 1 ;
        if ( abs( ret[ mid ].x - x ) < esp ) return ret[ mid ].y ;
        if ( x < ret[ mid ].x ) right = mid ; else left = mid ;
    }
    line temp ;
    temp.oper( ret[ left ] , ret[ right ] ) ;
    return temp.cal( x ) ;
}
   
ld calheight( ld x ) {
    ld h1 = calh( x , 1 , M , pos ) , h2 = calh( x , 1 , n , p ) ;
    return h1 - h2 ;
}
   
int main(  ) {
    scanf( "%d" , &n ) ;
    rep( i , n ) {
        double x ; scanf( "%lf" , &x ) ;
        p[ i ].x = ld( x ) ;
    }
    rep( i , n ) {
        double y ; scanf( "%lf" , &y ) ;
        p[ i ].y = ld( y ) ;
    }
    rep( i , n - 1 ) li[ ++ m ].oper( p[ i ] , p[ i + 1 ] ) ;
    sort( li + 1 , li + m + 1 ) ;
    rep( i , m ) {
        if ( abs( li[ i ].k - li[ i - 1 ].k ) <= esp ) continue ;
        while ( Top > 1 ) {
            point temp = st[ Top ].cross( li[ i ] ) ;
            if ( st[ Top - 1 ].cal( temp.x ) >= temp.y ) -- Top ;
            else break ;
        }
        st[ ++ Top ] = li[ i ] ;
    } 
    rep( i , Top ) {
        point temp = st[ i ].cross( st[ i + 1 ] ) ;
    }
    int left = 1 , right = Top ;
    while ( left < right ) {
        point temp = st[ left ].cross( st[ left + 1 ] ) ;
        if ( temp.x <= p[ 1 ].x ) ++ left ; else break ;
    }
    while ( left < right ) {
        point temp = st[ right ].cross( st[ right - 1 ] ) ;
        if ( temp.x >= p[ n ].x ) -- right ; else break ;
    }
    pos[ ++ M ].oper( p[ 1 ].x , st[ left ].cal( p[ 1 ].x ) ) ;
    for ( int i = left ; i < right ; ++ i ) {
        pos[ ++ M ] = st[ i ].cross( st[ i + 1 ] ) ;
    }
    pos[ ++ M ].oper( p[ n ].x , st[ right ].cal( p[ n ].x ) ) ;
    ld ans = inf ;
    rep( i , M ) ans = min( ans , calheight( pos[ i ].x ) ) ;
    rep( i , n ) ans = min( ans , calheight( p[ i ].x ) ) ;
    printf( "%.3f\n" , double( ans + esp ) ) ;
    return 0 ;
}