注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4946 Area of Mushroom  

2014-08-14 21:30:46|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4946
题意:二维平面上有几个student,给出坐标和移动速度,问每个stu移动范围是不是无限的(如果该学生是最先到的则认为是专属的移动区域)。
题解:如果速度不是最大的则移动范围一定有限,因为平面够大,只要距离够大一定会被速度大的超过。
剩下一堆速度最大的点,求凸包即可,在凸包里的移动范围有限,凸包上的无限。
需要注意的是:
如果点落在凸包相邻两个点之间也是无限的(这类点不会算在凸包内);
如果凸包上有重点,则这两个点都是有限的(题目要求是严格的超越);
如果所有点最大值是0,则所有点都有限。

struct point{
double x,y,v;
}p[N],res[N],f[N];
int tot,n;

bool operator < (const point &l, const point &r){
return l.y < r.y || (l.y == r.y && l.x < r.x);
}
double dist(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int mult(point sp, point ep, point op){
return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y);
}

int graham(point pnt[], int n, point res[])
{
int i, len, top = 1;
sort(pnt, pnt + n);
if (n == 0) return 0; res[0] = pnt[0];
if (n == 1) return 1; res[1] = pnt[1];
if (n == 2) return 2; res[2] = pnt[2];
for (i = 2; i < n; i++)
{
while (top && mult(pnt[i], res[top], res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n - 2];
for (i = n - 3; i >= 0; i--)
{
while (top!=len && mult(pnt[i], res[top],res[top-1]))
top--;
res[++top] = pnt[i];
}
return top;
}

int Find(int tmp,int pos)
{
for(int i=0;i<tmp;i++)
{
if(res[i].x == f[pos].x && res[i].y == f[pos].y && res[i].v == f[pos].v)
return 1;
}
return 0;
}

int Find2(int n,int pos)
{
for(int i=0;i<n;i++)
{
if(i!=pos && f[i].x == f[pos].x && f[i].y == f[pos].y && f[i].v == f[pos].v)
return 1;
}
return 0;
}

int jud(int tmp,int pos)
{
for(int i=1;i<tmp;i++)
{
if(mult(res[i],res[i-1],f[pos]))
return 1;
}
if(mult(res[0],res[tmp-1],f[pos]))
return 1;
return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int n,cas=1;
while(sf(n)!=EOF && n)
{
printf("Case #%d: ",cas++);
double cnt=-1;
fr(n){
scanf("%lf%lf%lf",&f[i].x,&f[i].y,&f[i].v);
cnt=max(cnt,f[i].v);
}
if(cnt == 0)
{
fr(n) printf("0");
pfn;
continue;
}
tot=0;
fr(n){
if(f[i].v == cnt)
p[tot++]=f[i];
}
int tmp=graham(p,tot,res);
fr(n){
if(f[i].v < cnt)
printf("0");
else
{
if(Find(tmp,i)) //是凸包上的点
{
if(Find2(n,i)) printf("0"); //是否有重点
else printf("1");
}
else
{
if(jud(tmp,i)) //判断点是否在凸包边界上
{
if(Find2(n,i))
printf("0");
else
printf("1");
}
else
printf("0");
}
}
}
pfn;
}
return 0;
}


  评论这张
 
阅读(108)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017