本文主要是介绍【HDU】5033 Building 单调栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】5033 Building
题目分析：就单调栈用叉积左右维护一个上凸壳就好了。。。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std ;typedef long long LL ;#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define rev( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define clr( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , 100000
#define rt o , l , rconst int MAXN = 100005 ;
const double eps = 1e-8 ;
const double pi = acos ( -1.0 ) ;struct Point {double x , y ;int idx ;Point () {}Point ( double x , double y ) : x ( x ) , y ( y ) {}bool operator < ( const Point& p ) const {return x < p.x ;}Point operator - ( const Point& p ) const {return Point ( x - p.x , y - p.y ) ;}
} S[MAXN << 1] , p[MAXN << 1] ;int top , cnt ;
int n , q ;
double ans[MAXN] ;int dcmp ( double x ) {return ( x > eps ) - ( x < -eps ) ;
}int cross ( const Point& a , const Point& b ) {return dcmp ( a.x * b.y - a.y * b.x ) ;
}void solve () {double x , y ;top = cnt = 0 ;scanf ( "%d" , &n ) ;rep ( i , 0 , n ) {scanf ( "%lf%lf" , &x , &y ) ;p[cnt] = Point ( x , y ) ;p[cnt].idx = -1 ;++ cnt ;}scanf ( "%d" , &q ) ;rep ( i , 0 , q ) {scanf ( "%lf" , &x ) ;p[cnt] = Point ( x , 0 ) ;p[cnt].idx = i ;++ cnt ;}sort ( p , p + cnt ) ;rep ( i , 0 , cnt ) {while ( top > 1 && cross ( S[top - 1] - p[i] , S[top - 2] - p[i] ) <= 0 ) -- top ;if ( ~p[i].idx ) {double x = p[i].x - S[top - 1].x ;double y = S[top - 1].y ;ans[p[i].idx] = atan ( x / y ) * 180.0 / pi ;} else S[top ++] = p[i] ;}top = 0 ;rev ( i , cnt - 1 , 0 ) {while ( top > 1 && cross ( S[top - 1] - p[i] , S[top - 2] - p[i] ) >= 0 ) -- top ;if ( ~p[i].idx ) {double x = S[top - 1].x - p[i].x ;double y = S[top - 1].y ;ans[p[i].idx] += atan ( x / y ) * 180.0 / pi ;} else S[top ++] = p[i] ;}rep ( i , 0 , q ) printf ( "%.10f\n" , ans[i] ) ;
}int main () {int T , cas = 0 ;scanf ( "%d" , &T ) ;while ( T -- ) {printf ( "Case #%d:\n" , ++ cas ) ;solve () ;}return 0 ;
}这篇关于【HDU】5033 Building 单调栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
