強烈推薦此題！這個題目我做了很久，始終不得其解。后來我向dm求教，他發來代碼。我對照數據才過的。
先考察一下這個問題的性質。
性質1：任何一個圓都覆蓋了一個閉區域。
性質2：對于任意一個點，覆蓋它的最上面的那個圓，一定是可見的。
性質3：如果一個圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
性質4：n 個圓最多有2(n-1)
2個交點，這些交點把 n 個圓分成最多2(n-1)
2條小圓弧。
性質5：對于每個小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
根據性質1和性質2，問題轉化為恰當地找出一些點，對于每個點，把覆蓋它的最上面的圓標記為可見。
根據性質3，這些點一定在所有圓的邊界集合內。
根據性質5，所有小圓弧構成邊界集合。每個小圓弧上只要任意取一個點就能代表整個小圓?。ㄟ吔纾?。不妨取中點。
至此得到算法：取所有小圓弧的中點，對每個點找到覆蓋它的最上面的圓。
根據性質4，最多取2(n-1)
2個點。對每個點找到覆蓋它的最上面的圓，需要O(n)次運算。總復雜度是O(n
3)。
其實此算法還有冗余，有些內部小圓弧可以不用考慮，但是我沒想出怎么優化。有誰知道更好的算法，請聯系我。blog留言或者qq交談或者發郵件都可以。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-8-24 12:33:03
File Name: pku1418.cpp
Description:
************************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <cmath>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
typedef complex <double> xy;
const double PI = acos(-1.0);
double normalize(double r)
{
while (r < 0.0) r += 2 * PI;
while (r >= 2 * PI) r -= 2 * PI;
return r;
}
int highest_cover(xy p, vector <xy> &points, vector <double> &rs)
{
for (int i = rs.size() - 1; i >= 0; i--)
if (abs(points[i] - p) < rs[i])
return i;
return -1;
}
int main()
{
while (1)
{
int n;
cin >> n;
if (!n) break;
vector <xy> points;
vector <double> rs;
for (int i = 0; i < n; i++)
{
double x, y, r;
cin >> x >> y >> r;
points.push_back(xy(x, y));
rs.push_back(r);
}
vector <bool> visible(n, false);
for (int i = 0; i < n; i++)
{
vector <double> rads;
rads.push_back(0.0);
rads.push_back(2.0 * PI);
for (int j = 0; j < n; j++)
{
double a = rs[i];
double b = abs(points[j] - points[i]);
double c = rs[j];
if (a + b < c || a + c < b || b + c < a) continue;
double d = arg(points[j] - points[i]);
double e = acos((a * a + b * b - c * c) / (2 * a * b));
rads.push_back(normalize(d + e));
rads.push_back(normalize(d - e));
}
sort(rads.begin(), rads.end());
for (int j = 0; j < rads.size() - 1; j++)
{
double rad = (rads[j + 1] + rads[j]) / 2.0;
double diff = 4E-13;
for (int k = -1; k <= 1; k += 2)
{
int t = highest_cover(xy(points[i].real() + (rs[i] + diff * k) * cos(rad),
points[i].imag() + (rs[i] + diff * k) * sin(rad)),
points, rs);
if (t != -1) visible[t] = true;
}
}
}
int ans = 0;
for (int i = 0; i < n; i++)
if (visible[i])
ans++;
cout << ans << endl;
}
return 0;
}