题目描述

有n个圆盘从天而降,后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.

输入

第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

输出

最后的周长,保留三位小数

样例输入

2
1 0 0
1 1 0

样例输出

10.472


题解

计算几何

考虑从下到上的每一个圆,它被其它的圆覆盖了多少。即考虑它被覆盖了多少弧度。

考虑两个圆,如果相离则不覆盖,内含判断一下包含关系。

如果它们相交,则两个半径和圆心连线形成了一个三角形,使用余弦定理$a^2+b^2-c^2=2ab\cos C$可以求出交点与圆心连线的夹角,再用$atan2$求出极角,极角加减夹角即为覆盖弧度。

得到所有覆盖弧度范围后排序,求区间覆盖即可。

注意一下覆盖弧度范围跨越0和2π的处理。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1010
#define squ(x) ((x) * (x))
using namespace std;
const double pi = acos(-1);
struct data
{
double pl , pr;
bool operator<(const data &a)const {return pl < a.pl;}
}a[N << 1];
double x[N] , y[N] , r[N];
int tot;
int main()
{
int n , i , j;
double afa , beta , d , last , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf%lf" , &r[i] , &x[i] , &y[i]);
for(i = 1 ; i <= n ; i ++ )
{
ans += 2 * pi * r[i];
tot = 0;
for(j = i + 1 ; j <= n ; j ++ )
{
tot ++ , d = squ(x[i] - x[j]) + squ(y[i] - y[j]);
if(squ(r[i] + r[j]) <= d) a[tot].pl = a[tot].pr = 0;
else if(squ(r[i] - r[j]) >= d)
{
if(r[i] > r[j]) a[tot].pl = a[tot].pr = 0;
else a[tot].pl = 0 , a[tot].pr = 2 * pi;
}
else
{
afa = acos((r[i] * r[i] + d - r[j] * r[j]) / (2 * r[i] * sqrt(d)));
beta = atan2(y[j] - y[i] , x[j] - x[i]);
if(beta < 0) beta += 2 * pi;
a[tot].pl = beta - afa , a[tot].pr = beta + afa;
if(a[tot].pl < 0) tot ++ , a[tot].pl = a[tot - 1].pl + 2 * pi , a[tot - 1].pl = 0 , a[tot].pr = 2 * pi;
else if(a[tot].pr > 2 * pi) tot ++ , a[tot].pr = a[tot - 1].pr - 2 * pi , a[tot - 1].pr = 2 * pi , a[tot].pl = 0;
}
}
sort(a + 1 , a + tot + 1);
last = -1;
for(j = 1 ; j <= tot ; j ++ )
{
if(a[j].pr <= last) continue;
if(a[j].pl > last) ans -= (a[j].pr - a[j].pl) * r[i];
else ans -= (a[j].pr - last) * r[i];
last = a[j].pr;
}
}
printf("%.3lf\n" , ans);
return 0;
}

最新文章

  1. 【一起学OpenFoam】01 OpenFoam的优势
  2. 06.GitHub实战系列~6.过滤器过滤掉的文件如何上传
  3. leetcode日记 Product of Array Except Self
  4. Masonry(AutoLayout)的使用
  5. WD硬盘型号信息
  6. zabbix配置发送报警邮件
  7. EXE中释放文件
  8. myeclipse svn配置
  9. 使用git的正确姿势
  10. money 和 smallmoney
  11. css倒三角的几种实现方式
  12. 安装XP和Ubuntu双系统问题——Ubuntu安装时无法识别原有系统
  13. Java单例模式的各种实现(饿汉、懒汉、静态内部类、static代码块、enum枚举类型)
  14. 初识Vue.js
  15. win10 UWP读写文件
  16. C语言的引用计数与对象树
  17. 【56】java本地文件File类详解
  18. Android事件机制之二:onTouch详解
  19. (转)医疗IT运维系统
  20. 非对称加密算法-RSA算法

热门文章

  1. Xamarin 常见问题解决方案汇总
  2. Python-OpenCV中的cv2.inpaint()函数
  3. mybatis(一):思维导图
  4. VA助手添加扩展文件后缀名
  5. Redis的安装以及spring整合Redis时出现Could not get a resource from the pool
  6. 中英文字符串截取函数msubstr
  7. Python——数据类型
  8. iOS开发中的Self-Manager 模式
  9. Bzoj 3450: Tyvj1952 Easy (期望)
  10. 【贪心 计数 倍增】bzoj4458: GTY的OJ