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

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

xmu 1228.数值随机算法——小型花园  

2011-11-12 12:42:12|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
1228.数值随机算法——小型花园
Time Limit: 3000 MS         Memory Limit: 65536 K
Total Submissions: 258 (70 users)         Accepted: 118 (70 users)
[ My Solution ]

Description

    TheBeet有一片小花园,这个花园非常小,只有长宽都是1米。同时TheBeet又是出了名的懒,他从来不给这片花园里面的花浇水。当然,为了保证花的存活,TheBeet在花园中安装了几个小型自动喷灌系统,每个喷灌系统都能为其周围范围r内的花浇水。现在问题来了,TheBeet想知道他的花园中有多少地方是适合种植的——即至少有一个喷灌系统能覆盖到。

Input

    输入第一行为一正整数m(m<=10),表示喷灌系统的个数。
    接下来m行每行3个实数描述一个喷灌系统,分别是x y r(0<= x, y <= 1,  0< r<=1),表示喷灌系统的位置和覆盖半径。

Output

    输出一个实数表示喷灌系统能覆盖到的面积。尽可能的精确,如果您的答案在与精确解相差在0.01内,则被认为是正确解。

Sample Input

4
0.6 0.6 0.6
0 0.5 0.5
0.2 0.2 0.2
0.8 0.8 0.6

Sample Output

0.97124

Source
xmu
 
如果求覆盖的总面积减去重叠的面积和出了1m以外的面积,可想而知,计算量很大,考虑的肯定不是很全面。转而一想,因为误差为0.01.所以把每一个数多*100.则都变成了整数,而开一个a【100】【100】的数组初值为0。然后遍历每一个数组到圆心的距离如果《=半径的话就把数组标记一下1为覆盖的。最后遍历数组a中1的个数/10000就是最终的答案了。
 
#include <stdio.h>
#include <math.h>
#include <string.h>
struct fountain
{
 double x;
 double y;
 double r;
}f[11];
inline double dis(double x1, double y1, double x2, double y2)
{
 return sqrt( (x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) );
}
int main()
{
 int n, i, j, a[100][100];
 memset(a, 0, sizeof(a));
 scanf("%d", &n);
 for(i = 0; i < n; i++)
 {
  scanf("%lf%lf%lf", &f[i].x, &f[i].y, &f[i].r);
  f[i].x *= 100;
  f[i].y *= 100;
  f[i].r *= 100;
 }
  double sum = 0;
  for(int ii = 0; ii < n; ii++)
  for(i = 0; i < 100; i++)
   for(j = 0; j < 100; j++)
    if(dis(i, j, f[ii].x, f[ii].y) <= f[ii].r)
     a[i][j] = 1;
 for(i = 0; i < 100; i++)
  for(j = 0; j < 100; j++)
   if(a[i][j] == 1)
    sum += 1;
 printf("%lf\n", sum /10000.0);
return 0;
}
  评论这张
 
阅读(109)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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