HDU5033

真蠢，和网络赛的时候我WA掉的思想已经很接近了，被他们又是说这说那的绕进去了，就是一个单调栈，栈中元素的纵坐标严格降低，并且栈中顶部两点之间斜率的绝对值要小于栈顶点和入栈点的斜率。这样是一个向上凸的图形（如果不考虑后面一个条件，是下凹凸都有的奇怪图形图形，后面计算最近切点时不满足性质，效率会退化），当查询点找到最近切点（姑且称作最近似切点，理解就知道我说的是什么意思了）时，这个点代表的楼房就是影响视线的房子，正向、反向各扫一下，有点离线查询的意思就能得出结果。

原谅我语言表述能力有限。

其实，如果数据出现特殊的V字型，这种方法也许就T了，也许还有更好的我不知道的方法吧。

/****************************************************
file name: 5033.cpp
author: huangjipeng
creat time: 2014年09月21日 星期日 18时53分55秒
***************************************************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ls (p<<1)
#define rs (ls|1)
#define mid ((tree[p].l+tree[p].r)>>1)
#define MAXN 1
typedef long long ll;
struct point
{
double x,y;
int id;
}node[200005];
int q,n;
double qx[100005];
int l[100005],r[100005];
bool cmp(const struct point &a,const struct point &b)
{
return a.x<b.x;
}
int top=1;
int que[100005];
void op(int now)
{
while(top>=1 && node[que[top-1]].y<=node[now].y)
top--;
while(top>1 && ((node[now].y-node[que[top-1]].y)*fabs(node[que[top-1]].x-node[que[top-2]].x))>=(node[que[top-1]].y-node[que[top-2]].y)*fabs(node[now].x-node[que[top-1]].x))
top--;
que[top++]=now;
}
void solve()
{
node[0].x=node[0].y=0;
top=1;
que[0]=0;
for(int i=1;i<=(q+n);i++)
{
if(node[i].y>0)
op(i);
else
{
while(top>1 && node[que[top-1]].y*fabs(node[i].x-node[que[top-2]].x)<=(node[que[top-2]].y)*fabs(node[i].x-node[que[top-1]].x))
top--;
l[node[i].id]=que[top-1];
}
}
node[q+n+1].x=node[q+n].x+1;
node[q+n+1].y=0;
top=1;
que[0]=q+n+1;
for(int i=q+n;i>=1;i--)
{
if(node[i].y>0)
op(i);
else
{
while(top>1 && node[que[top-1]].y*fabs(node[i].x-node[que[top-2]].x)<=(node[que[top-2]].y)*fabs(node[i].x-node[que[top-1]].x))
top--;
r[node[i].id]=que[top-1];
}
}
}
int main()
{
int t;
cin>>t;
for(int te=1;te<=t;te++)
{
top=1;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&node[i].x,&node[i].y);
cin>>q;
for(int i=1;i<=q;i++)
{
scanf("%lf",&node[i+n].x);
qx[i]=node[i+n].x;
node[i+n].y=0;
node[i+n].id=i;
}
sort(node+1,node+n+q+1,cmp);
solve();
printf("Case #%d:n",te);
for(int i=1;i<=q;i++)
{
// cout<<l[i]<<" "<<r[i]<<" "<<qx[i]<<endl;
printf("%.10fn",180-180*(atan(node[l[i]].y/fabs(qx[i]-node[l[i]].x))+atan(node[r[i]].y/fabs(qx[i]-node[r[i]].x)))/acos(-1));
}
}
return 0;
}

最后

以上就是勤恳河马为你收集整理的HDU5033的全部内容，希望文章能够帮你解决HDU5033所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。