题目大意

n个圆盘依次放在桌面上,给出每个圆盘的坐标和圆心,求能看见的圆的个数;

分析

圆的每个可见部分由小圆弧围成,因此可以先求出所有小圆弧,然后判断每段小圆弧内外两侧的可见圆盘.具体来说,把小圆弧中点往内外两侧各移动很小距离,得到两个点,然后标记包含这两个点的圆盘中最顶部的那个为可见的;

算法实现

离散化求出与一个圆的所有交点的弧度,排序后, 两个相邻的交点之间 只有 一个 弧,在求这个弧的中点,分别向内外移动,判断哪些圆盘是可见的。

#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <algorithm>
using namespace std;
#define PI acos(-1)
#define eps 5e-13
int N;
struct Point
{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
};
struct Circle
{
	Point c;
	double r;
	Circle(){}
	Circle(Point c,double r):c(c),r(r){}
	Point point(double a)
	{
		return Point(c.x+r*cos(a),c.y+r*sin(a));
	}
}Cir[110];


int dcmp(double x)
{
	if(fabs(x)<eps)return 0;
	else return x<0?-1:1;
}
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);  }
Point operator*(Point A,double p){  return Point(A.x*p,A.y*p);      }
Point operator/(Point A,double p){  return Point(A.x/p,A.y/p);   }
bool operator<(const Point&a,const Point&b){  return a.x<b.x||(a.x==b.x&&a.y<b.y);  }
bool operator == (const Point&a,const Point&b){  return dcmp(a.x-b.x)==0&&dcmp(a.x-b.x)==0;  }
double Dot(Point A,Point B){return A.x*B.x+A.y*B.y;}
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
double Length(Point A){return sqrt(Dot(A,A));}
double angle(Point A){return atan2(A.y,A.x);}
int  getCircleCircleIntersection(Circle C1,Circle C2,vector<double> &sol)
{
	double d=Length(C1.c-C2.c);
	if(dcmp(d)==0)
	{
		if(dcmp(C1.r-C2.r)==0)return -1;
		else return 0;
	}
	if(dcmp(C1.r+C2.r-d)<0)return 0;
	if(dcmp(fabs(C1.r-C2.r)-d)>0)return 0;
	double a=angle(C2.c-C1.c);
	double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));
	sol.push_back(a-da);
	if(dcmp(da))
	{
		sol.push_back(a+da);
		return 2;
	}
	else return 1;
}
int topmost(Point p)
{
	int ans=-1;
	for(int i=N-1;i>=0;i--)
		if(Length(p-Cir[i].c)<Cir[i].r)
		{
			ans=i;
			break;
		}
	return ans;
}
int main()
{
	while(cin>>N&&N!=0)
	{
		for(int i=0;i<N;i++)
			cin>>Cir[i].c.x>>Cir[i].c.y>>Cir[i].r;
		set<int> ret;
		for(int i=0;i<N;i++)
		{
			vector<double> sol;
			for(int j=0;j<N;j++)
				getCircleCircleIntersection(Cir[i],Cir[j],sol);
			sol.push_back(0);
			sol.push_back(2.0*PI);
			sort(sol.begin(),sol.end());
			int size=sol.size();
			for(int j=0;j<size;j++)
			{
				double mid=(sol[j]+sol[j+1])/2;
				for(int d=-1;d<=1;d=d+2)
				{
					double r2=Cir[i].r+eps*d;
					Point p=Point(Cir[i].c.x+r2*cos(mid),Cir[i].c.y+r2*sin(mid));
					int t=topmost(p);
					if(t>=0)ret.insert(t);
				}
			}
		}
		cout<<ret.size()<<endl;
	}
	return 0;
}