题意:

把n个圆盘依次放到桌面上,按照放置的先后顺序给出这n个圆盘的圆心和半径,输出有多少个圆盘可见(即未被全部覆盖)。

分析:

题中说对输入数据进行微小扰动后答案不变。

所露出的部分都是由若干小圆弧组成的。因此求出每个圆与其他圆相交的小圆弧,取圆弧的终点,分别向里和向外移动一个很小的距离的到P'。标记包含P'的最上面的那个圆为可见。

 //#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const int maxn = ;
const double PI = acos(-1.0);
const double Two_PI = PI * ;
const double eps = * 1e-;
int n;
double radius[maxn];
bool vis[maxn]; int dcmp(double x)
{
if(fabs(x) < eps) return ;
else return x < ? - : ;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y) {}
};
typedef Point Vector;
Point operator + (Point A, Point B) { return Point(A.x+B.x, A.y+B.y); }
Point operator - (Point A, Point B) { return Point(A.x-B.x, A.y-B.y); }
Vector operator * (Vector A, double p){ return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p){ return Vector(A.x/p, A.y/p); }
Point center[maxn]; double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
double Length(Vector A){ return sqrt(Dot(A, A)); }
double angle(Vector v) { return atan2(v.y, v.x); }
double NormalizeAngle(double rad)
{//将所求角度化到0到2π之间
return rad - Two_PI*(floor(rad/Two_PI));
} void getCCIntersection(Point c1, double r1, Point c2, double r2, vector<double>& rad)
{
double d = Length(c1 - c2);
if(dcmp(d) == ) return;
if(dcmp(d-r1-r2) > ) return;
if(dcmp(d-fabs(r1-r2)) < ) return; double a = angle(c2-c1);
double ag = acos((r1*r1+d*d-r2*r2)/(*r1*d));
rad.push_back(NormalizeAngle(a + ag));
rad.push_back(NormalizeAngle(a - ag));
} int topmost(Point P)
{
for(int i = n-; i >= ; --i)
if(Length(P-center[i]) < radius[i]) return i;
return -;
} int main(void)
{
#ifdef LOCAL
freopen("2572in.txt", "r", stdin);
#endif while(scanf("%d", &n) == && n)
{
for(int i = ; i < n; ++i)
scanf("%lf%lf%lf", &center[i].x, &center[i].y, &radius[i]);
memset(vis, , sizeof(vis)); for(int i = ; i < n; ++i)
{
vector<double> rad;
rad.push_back(0.0);
rad.push_back(Two_PI);
for(int j = ; j < n && j != i; ++j)
getCCIntersection(center[i], radius[i], center[j], radius[j], rad);
sort(rad.begin(), rad.end()); for(int j = ; j < rad.size() - ; ++j)
{
double mid = (rad[j] + rad[j+]) / 2.0;
for(int side = -; side <= ; side += )
{
double r = radius[i] + side*eps;
int t = topmost(Point(center[i].x+r*cos(mid), center[i].y+r*sin(mid)));
if(t >= ) vis[t] = true;
}
}
}
int ans = ;
for(int i = ; i < n; ++i) if(vis[i]) ++ans;
printf("%d\n", ans);
} return ;
}

代码君

最新文章

  1. linux 文件系统
  2. PHP 分页函数
  3. mssql 获取自增列起始及增量
  4. C++文件流类与文件流对象
  5. sybase ODBC驱动
  6. [BZOJ 3143][HNOI2013]游走(数学期望)
  7. ArcGIS Engine开发之旅01---产品组成、逻辑体系结构
  8. js获取IP地址方法总结_转
  9. Codeforces Round #330 (Div. 2) A. Vitaly and Night 暴力
  10. Java反射_JDBC操作数据
  11. UVA 297 Quadtrees(四叉树建树、合并与遍历)
  12. 使用IDENTITY列属性和Sequence对象
  13. Java中的statickeyword具体解释
  14. word文档自动生成方法
  15. BZOJ_5249_Luogu_P4364_[2018多省省队联测]_IIIDX_九省联考2018_JLOI2018_线段树
  16. OO第一单元(求导)单元总结
  17. ThinkPHP框架整合phpqrcode生成二维码DEMO
  18. window下强制删除文件
  19. python中的异常处理常用方法
  20. Linux 内核 hlist 详解

热门文章

  1. 一点关于Ajax和一个等待图标的显示
  2. 送给那些喜欢myeclipse黑色主题但是又不知道怎么配色的人
  3. BZOJ 1854: [Scoi2010]游戏 无向图判环
  4. Codeforces Round #352 (Div. 2) D. Robin Hood
  5. 01-03-03【Nhibernate (版本3.3.1.4000) 出入江湖】cascade的测试
  6. Error: Exception in thread “main” java.lang.NoClassDefFoundError错误
  7. Unity3D脚本中文系列教程(三)
  8. linux源代码阅读笔记 find_entry分析
  9. IOS委托设计模式(摘自IOS开发指南)
  10. POJ1426Find The Multiple