首页 > 代码库 > HDU 5033 Building

HDU 5033 Building

2024-07-24 00:30:49   221人阅读

 

Building

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1011    Accepted Submission(s): 281
Special Judge

Problem Description
Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position xi with its height hi. All skyscrapers located in different place. The skyscrapers had no width, to make it simple. As the skyscrapers were so high, Matt could hardly see the sky.Given the position Matt was at, he wanted to know how large the angle range was where he could see the sky. Assume that Matt‘s height is 0. It‘s guaranteed that for each query, there is at least one building on both Matt‘s left and right, and no building locate at his position.
 

 

Input
The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

Each test case begins with a number N(1<=N<=10^5), the number of buildings.

In the following N lines, each line contains two numbers, xi(1<=xi<=10^7) and hi(1<=hi<=10^7).

After that, there‘s a number Q(1<=Q<=10^5) for the number of queries.

In the following Q lines, each line contains one number qi, which is the position Matt was at.
 

 

Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1).

Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).
 

 

Sample Input
331 22 15 11431 32 25 11431 42 35 114
 

 

Sample Output
Case #1:
101.3099324740
Case #2:
90.0000000000
Case #3:
78.6900675260
 
 
左右分别维护一个递减的凸包 ，然后求一下角度就过了 0，0

 

 

#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstdio>using namespace std;typedef long long LL;#define PI acos(-1.0)#define eps 1e-8const int N = 200100;int n , m ;struct node{    double x, y ;    node (){};    node operator - (const node &a )const{        node res ;res.x = x - a.x , res.y = y- a.y; return res;    }}Q[N],e[N],ch[N];inline bool cmp1(const node &a ,const node &b ){ return a.x < b.x ;}inline bool cmp2(const node &a ,const node &b ){ return a.y < b.y ;}inline double Cross( node a ,node b ){ return a.x * b.y - a.y * b.x ; }double L[N] , R[N] ;double cal( node a ,node b ){ return  max( 0.0, atan( fabs( a.y - b.y ) / fabs( a.x - b.x ) ) * 180.0 / PI ); }void solve(){    int top = 0 ;    for( int i = 0 ; i < n ; ++ i ) {        while( top > 0 && e[i].y >= ch[top-1].y ) top--;        while( top > 1 && Cross( ch[ top - 1 ] - ch[ top -2 ] , e[i] - ch[ top - 2 ] ) >= 0 ) top-- ;        ch[ top++ ] = e[i];        if( top == 1 )  L[i] = 0 ; else  L[i] = cal( ch[top-2] , ch[top-1] );    }    top = 0 ;    for( int i = n - 1 ; i >= 0  ;--i ){        while( top > 0 && e[i].y >= ch[top-1].y ) top--;        while( top > 1 &&   Cross( ch[ top - 1 ] - ch[ top -2 ] , e[i] - ch[ top - 2 ] ) <= 0 ) top--;        ch[ top ++ ] = e[i];        if( top <= 1 ) R[i] = 0; else R[i] = cal(ch[top-2],ch[top-1]);    }    int tot = 0 ;    for(int i = 0 ; i < n ; ++i ){        if( Q[tot].x == e[i].x ){            Q[tot++].x = 180.0 -L[i] -R[i] ;        }        if(tot == m )break;    }}void run(){    scanf("%d",&n);    for( int i = 0; i < n ; ++i ){        scanf("%lf%lf",&e[i].x, &e[i].y);    }    scanf("%d",&m);    for(int i = 0 ; i < m ; ++i ){        scanf("%lf",&Q[i].x);        Q[i].y = i ;        e[ n + i ].x = Q[i].x ;        e[ n + i ].y = 0 ;    }    n += m ;    sort(Q,Q+m,cmp1);   sort(e,e+n,cmp1);    solve();    sort(Q,Q+m,cmp2);    for( int i = 0 ; i < m ; ++i ){        printf("%.10lf\n",Q[i].x);    }}int main(){    #ifdef LOCAL        freopen("in","r",stdin);    #endif    int cas = 1 ,_ ;    scanf("%d",&_) ;    while(_--)    {        printf("Case #%d:\n",cas++);        run();    }    return 0;}

 

HDU 5033 Building


联系
我们