一次放下n个圆
问最终可见的圆的数量
应该是比较经典的问题吧
考虑一个圆与其他每个圆的交点O(n)个
将其割成了O(n)条弧
那么看每条弧的中点 分别向内向外调动eps这个点 则最上面的覆盖这个点的圆可见O(n)
总时间复杂度O(n ** 3)
怕炸精度,代码基本抄的rjl的
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector> using namespace std; typedef double data_type; const data_type eps = * 1e-;
int dcmp(const data_type& x) {
if(fabs(x) < ) return ; return x < ? - : ;
} const data_type pi = acos(-1.0), dpi = * acos(-1.0); double NormalizeAngle(double rad) {
return rad - dpi * floor(rad / dpi);
} typedef const struct Point& Point_cr;
typedef struct Point {
data_type x, y;
Point() {}
Point(data_type x, data_type y) : x(x), y(y) {}
Point operator + (Point_cr rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (Point_cr rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
Point operator * (data_type k) const {
return Point(x * k, y * k);
}
Point operator / (double k) const {
return Point(x / k, y / k);
}
double length() const {
return hypot(x, y);
}
double angle() const {
return atan2(y, x);
}
}Vector; double Dot(const Vector& v1, const Vector& v2) {
return v1.x * v2.x + v1.y * v2.y;
} double length(const Vector& v) {
return sqrt(Dot(v, v));
} typedef const Vector& Vector_cr;
void CircleCircleIntersection(Point_cr c1, double r1, Point c2, double r2, vector<double> &rad) {
double d = (c1 - c2).length();
if(dcmp(d) == ) return;
if(dcmp(r1 + r2 - d) < ) return;
if(dcmp(fabs(r1 - r2) - d) > ) return;
double a = (c2 - c1).angle();
double da = acos((r1 * r1 + d * d - r2 * r2) / ( * r1 * d));
rad.push_back(NormalizeAngle(a + da));
rad.push_back(NormalizeAngle(a - da));
} const int N = + ;
int n;
Point centre[N];
double radius[N];
bool vis[N]; int topmost(Point p) {
for(int i = n - ; i >= ; i--) {
if((centre[i] - p).length() < radius[i]) return i;
}
return -;
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif while(scanf("%d", &n) == && n) {
for(int i = ; i < n; i++) {
double x, y, r;
scanf("%lf%lf%lf", &x, &y, &r);
centre[i] = Point(x, y);
radius[i] = r;
}
memset(vis, , sizeof vis);
for(int i = ; i < n; i++) {
vector<double> rad;
rad.push_back();
rad.push_back(dpi); for(int j = ; j < n; j++) {
CircleCircleIntersection(centre[i], radius[i], centre[j], radius[j], rad);
} sort(rad.begin(), rad.end()); for(unsigned j = ; j < rad.size(); j++) {
double mid = (rad[j] + rad[j+]) / 2.0;
for(int side = -; side <= ; side += ) {
double r2 = radius[i] - side * eps;
int t = topmost(Point(centre[i].x + cos(mid) * r2, centre[i].y + sin(mid) * r2));
if(t >= ) vis[t] = ;
}
}
}
int ans = ;
for(int i = ; i < n; i++) if(vis[i]) {
ans++;
}
printf("%d\n", ans);
} return ;
}