hdu 5033 Building(斜率優化)
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 x
i with its height h
i. 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, x
i(1<=x
i<=10^7) and h
i(1<=h
i<=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 q
i, 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
#include
#include
#include
#include
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.x0&&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
