首页 > 代码库 > hdu 5033 Building(斜率优化)

hdu 5033 Building(斜率优化)

2024-07-24 06:38:10   220人阅读

Building

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1237    Accepted Submission(s): 350
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
3
3
1 2
2 1
5 1
1
4
3
1 3
2 2
5 1
1
4
3
1 4
2 3
5 1
1
4
 

Sample Output
Case #1:
101.3099324740
Case #2:
90.0000000000
Case #3:
78.6900675260
 

Source
2014 ACM/ICPC Asia Regional Beijing Online
 

Recommend
hujie   |   We have carefully selected several similar problems for you:  5041 5040 5039 5038 5037 
 题意：
告诉你n(1e5)个建筑物的位置和高度。现在q(1e5)条询问。每次询问如果你站在x处。问你所能看到天空的角度。
x.y都为浮点数。
思路:
用单调队列维护一个上凸曲线。因为下凸曲线的凸点是不可能成为答案的。这个画画图就明白了。找答案时队列中答案之后建筑物都可以去掉了。因为都没有答案建筑物优。然后从左到右算一次。然后从右往左算一次。就可以算出每个询问的角度了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const int maxn=100010;
typedef long long ll;
struct node
{
    double x,y;
} bd[maxn],q[maxn],qu[maxn],le[maxn],ri[maxn];
int head,tail;
bool cmp(node a,node b)
{
    return a.x<b.x;
}
double ans[maxn];
int main()
{
    int t,cas=1,n,m,i,j,p;
    double x1,y1,x2,y2,per=180/PI;

    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%lf%lf",&bd[i].x,&bd[i].y);
        sort(bd,bd+n,cmp);
        scanf("%d",&m);
        for(i=0;i<m;i++)
            scanf("%lf",&qu[i].x),qu[i].y=i;
        sort(qu,qu+m,cmp);
        head=tail=j=0;
        for(i=0;i<m;i++)
        {
            for(;j<n&&bd[j].x<qu[i].x;j++)
            {
                while(tail-head>0&&bd[j].y>=q[tail-1].y)
                    tail--;
                while(tail-head>=2)
                {
                    p=tail-1;
                    x2=bd[j].x-q[p].x;
                    y2=bd[j].y-q[p].y;
                    x1=q[p].x-q[p-1].x;
                    y1=q[p].y-q[p-1].y;
                    if(x1*y2>=x2*y1)
                        tail--;
                    else
                        break;
                }
                q[tail].x=bd[j].x;
                q[tail++].y=bd[j].y;
            }
            if(tail-head==0)
                le[i].x=qu[i].x-1,le[i].y=0;
            else
            {
                while(tail-head>=2)
                {
                    p=tail-1;
                    x2=qu[i].x-q[p].x;
                    y2=-q[p].y;
                    x1=qu[i].x-q[p-1].x;
                    y1=-q[p-1].y;
                    if(x2*y1<=x1*y2)
                        tail--;
                    else
                        break;
                }
                le[i].x=q[tail-1].x;
                le[i].y=q[tail-1].y;
            }
        }
        head=tail=0,j=n-1;
        for(i=m-1;i>=0;i--)
        {
            for(;j>=0&&bd[j].x>qu[i].x;j--)
            {
                while(tail-head>0&&bd[j].y>=q[tail-1].y)
                    tail--;
                while(tail-head>=2)
                {
                    p=tail-1;
                    x2=bd[j].x-q[p].x;
                    y2=bd[j].y-q[p].y;
                    x1=q[p].x-q[p-1].x;
                    y1=q[p].y-q[p-1].y;
                    if(x2*y1>=x1*y2)
                        tail--;
                    else
                        break;
                }
                q[tail].x=bd[j].x;
                q[tail++].y=bd[j].y;
            }
            if(tail-head==0)
                ri[i].x=qu[i].x+1,ri[i].y=0;
            else
            {
                while(tail-head>=2)
                {
                    p=tail-1;
                    x2=qu[i].x-q[p].x;
                    y2=-q[p].y;
                    x1=qu[i].x-q[p-1].x;
                    y1=-q[p-1].y;
                    if(x1*y2<=x2*y1)
                        tail--;
                    else
                        break;
                }
                ri[i].x=q[tail-1].x;
                ri[i].y=q[tail-1].y;
            }
        }
        for(i=0;i<m;i++)
        {
            x1=le[i].x-qu[i].x;
            y1=le[i].y;
            x2=ri[i].x-qu[i].x;
            y2=ri[i].y;
            ans[int(qu[i].y)]=per*acos((x1*x2+y1*y2)/(sqrt(x1*x1+y1*y1)*sqrt(x2*x2+y2*y2)));
        }
        printf("Case #%d:\n",cas++);
        for(i=0;i<m;i++)
            printf("%.10f\n",ans[i]);
    }
    return 0;
}


hdu 5033 Building(斜率优化)


联系
我们