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
Case #1: 101.3099324740 Case #2: 90.0000000000 Case #3: 78.6900675260
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100000+100;
const double pi = acos(-1.0);
struct node
{
int x;
int h;
}a[maxn*2],stacks[maxn*2];
double ans[maxn];
int n,q;
bool cmp(node a,node b)
{
return a.x<b.x;
}
int cross(node a,node b,node c)//判断角的大小
{
if(c.h<0)
c.h=0;
return (long long)(c.x-b.x)*(a.h-c.h)>=(long long)(c.x-a.x)*(b.h-c.h);
}
double getangle(node a,node b)
{
return atan((double)(b.x-a.x)*1.0/(double)(a.h*1.0));
}
void solve()
{
int head=0;
for(int i=0;i<n+q;i++)
{
if(a[i].h<=0)
{
while(head>=2&&cross(stacks[head-2],stacks[head-1],a[i]))
{
head--;
}
ans[-a[i].h]+=getangle(stacks[head-1],a[i]);
}
else
{
while(head&&stacks[head-1].h<=a[i].h)
{
head--;
}
while(head>=2&&cross(stacks[head-2],stacks[head-1],a[i]))
{
head--;
}
stacks[head++]=a[i];
}
}
}
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i].x,&a[i].h);
}
scanf("%d",&q);
for(int i=0;i<q;i++)
{
scanf("%d",&a[i+n].x);
a[i+n].h=-i;
}
sort(a,a+n+q,cmp);
memset(ans,0,sizeof(ans));
solve();
reverse(a,a+n+q);//逆置
for(int i=0;i<n+q;i++)//从右往左
a[i].x = 10000000 - a[i].x;//保证前面的位置小于后面的,由于ans中存储的是查询的位置,不会影响答案。
solve();
printf("Case #%d:\n",ca++);
for(int i=0;i<q;i++)
{
printf("%.10f\n",ans[i]*180.0/pi);
}
}
return 0;
}
原文:http://blog.csdn.net/caduca/article/details/39507549