题目：
pdf：https://icpcarchive.ecs.baylor.edu/external/25/2572.pdf
依次给出n个圆的圆心坐标和半径，问最终可以看到多少个圆
解题思路：
题目特别指出了一个精度值5e-13，这并非是我们常设的eps（因为题目说了末尾最多12位），这个精度是为了避免出现两个圆的交点是一个点这种情况，若交点是一个点，其实这个点非常非常微小，我们无法判断它对最终答案的贡献。
同时这也说明同一个圆心的圆，半径为r-(5e-13)， r， r+(5e-13)的结果是一样的，是等价的。比如eps设1e-13，圆A（c，r），圆A圆弧左侧的点P1（r-(5e-13)）,圆弧右侧的点P2（r+(5e-13)），比如在圆A之后出现的圆B和P1或者P2相交，那么这两个圆就是相交的，相交部分不为空。
通过圆两两相交得到每个圆上所有交点对应的极角值，对一个圆上的两个相邻极角对应的点所形成的一段圆弧。最终可见的都是圆弧，两个交点确定两条圆弧，分别在多个圆上，以最先出现的圆为基准，判断它上面的圆是否覆盖了最先出现的圆上的圆弧，如果覆盖，那么另一条圆弧（或者说圆,存在全覆盖的情况）是可见的，做个标记。如何判断圆是否覆盖了一条圆弧呢，可以根据这个圆弧的中点来代替整条圆弧判断，故只需判断上述的P1/P2是否在圆内即可。特判圆无交点的情况。
圆A（c，r1）,圆B（c，r2），r1<r2，考虑两种情况，A先放，B后放 和 A后放B先放，结果是不一样的。
ac代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10;
const double eps = 1e-13;//eps用于控制精度,或者更高精度
const double pi = acos(-1.0);//pi
// 点
struct Point//点或向量
{
double x, y;
Point(double x = 0, double y = 0) :x(x), y(y) {}
friend bool operator < (Point a, Point b)
{
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
};
typedef Point Vector;
Vector operator + (Vector a, Vector b)//向量加法
{
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)//向量减法
{
return Vector(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);
}
int dcmp(double x)//精度三态函数(>0,<0,=0)
{
if (fabs(x) < eps)return 0; //等于
else return x < 0 ? -1 : 1;//小于，大于
}
bool operator == (const Point &a, const Point &b)//向量相等
{
return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;
}
//点的辅助函数
double Dot(Vector a, Vector b)//点积
{
return a.x * b.x + a.y * b.y;
}
double Cross(Vector a, Vector b)//外积
{
return a.x * b.y - a.y * b.x;
}
double Length(Vector a)//模
{
return sqrt(Dot(a, a));
}
Vector Rotate(Vector a, double rad)//逆时针旋转rad弧度
{
return Vector(a.x*cos(rad) - a.y*sin(rad), a.x*sin(rad) + a.y*cos(rad));
}
double Angle(Point a)//极角
{
return atan2(a.y, a.x);
}
double Distance(Point a, Point b)//两点间距离
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
struct Circle
{
Point c;
double r;
bool vis;
vector<double> rads;//存极角
Circle(Point c = Point(), double r = 0):c(c),r(r)
{
vis = false;
rads.clear();
}
Point point_in(double a)//基于极角求圆上一点坐标
{
double R = r + 5e-13;
return Point(c.x + cos(a)*R, c.y + sin(a)*R);
}
Point point_out(double a)
{
double R = r - 5e-13;
return Point(c.x + cos(a)*R, c.y + sin(a)*R);
}
};
//两圆交点,在板子上稍作修改
void getCirleCirleIntersection(Circle &C1, Circle &C2)//圆的交点的极角是圆的一个属性，已经和圆绑定到一起了
{
double d = Length(C1.c - C2.c);
if (dcmp(d) == 0) return ;//圆心重合
if (dcmp(C1.r + C2.r - d) < 0) return ;//相离
if (dcmp(fabs(C1.r - C2.r) - d) > 0) return ; //内含，圆心不重合
double a = Angle(C2.c - C1.c);
double da = acos((C1.r*C1.r + d * d - C2.r*C2.r) / (2 * C1.r*d));
C1.rads.push_back(a+da);
if (dcmp(da)!=0) C1.rads.push_back(a-da);
a = Angle(C1.c - C2.c);
da = acos((C2.r*C2.r+d*d-C1.r*C1.r)/(2*C2.r*d));
C2.rads.push_back(a+da);
if(dcmp(da)!=0) C2.rads.push_back(a-da);
}
Circle a[110];
int n, ans;
double x, y ,z;
void check(Point p)
{
for(int i = n-1; i >= 0; i--)
{
if(dcmp(Distance(p, a[i].c)-a[i].r) <= 0)
{
if(!a[i].vis)
{
a[i].vis = true;
ans++;
}
break;
}
}
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
while(scanf("%d", &n))
{
ans = 0;
if(n==0) break;
for(int i = 0; i < n; i++)
{
scanf("%lf %lf %lf", &x, &y, &z);
a[i] = Circle{Point(x, y), z};
}
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
getCirleCirleIntersection(a[i],a[j]);
for(int i = 0; i < n; i++)
{
if(a[i].rads.size() == 0) // 不和其他圆相交
{
check(a[i].point_in(0));
check(a[i].point_out(0));
}
else
{
sort(a[i].rads.begin(), a[i].rads.end());
a[i].rads.push_back(a[i].rads[0]);//再加2*pi
for(int j = 1; j < a[i].rads.size(); j++)
{
double ang = (a[i].rads[j] + a[i].rads[j - 1]) / 2.0;
check(a[i].point_in(ang));
check(a[i].point_out(ang));
}
}
}
printf("%d\n", ans);
}
return 0;
}
京公网安备 11010502036488号