強(qiáng)烈推薦此題！這個(gè)題目我做了很久，始終不得其解。后來我向dm求教，他發(fā)來代碼。我對(duì)照數(shù)據(jù)才過的。
先考察一下這個(gè)問題的性質(zhì)。
性質(zhì)1：任何一個(gè)圓都覆蓋了一個(gè)閉區(qū)域。
性質(zhì)2：對(duì)于任意一個(gè)點(diǎn)，覆蓋它的最上面的那個(gè)圓，一定是可見的。
性質(zhì)3：如果一個(gè)圓不可見（它被完全覆蓋），那么它的邊界是被完全覆蓋的。
性質(zhì)4：n 個(gè)圓最多有2(n-1)
2個(gè)交點(diǎn)，這些交點(diǎn)把 n 個(gè)圓分成最多2(n-1)
2條小圓弧。
性質(zhì)5：對(duì)于每個(gè)小圓弧，要么它全被覆蓋，要么它全不被覆蓋。
根據(jù)性質(zhì)1和性質(zhì)2，問題轉(zhuǎn)化為恰當(dāng)?shù)卣页鲆恍c(diǎn)，對(duì)于每個(gè)點(diǎn)，把覆蓋它的最上面的圓標(biāo)記為可見。
根據(jù)性質(zhì)3，這些點(diǎn)一定在所有圓的邊界集合內(nèi)。
根據(jù)性質(zhì)5，所有小圓弧構(gòu)成邊界集合。每個(gè)小圓弧上只要任意取一個(gè)點(diǎn)就能代表整個(gè)小圓?。ㄟ吔纾?。不妨取中點(diǎn)。
至此得到算法：取所有小圓弧的中點(diǎn)，對(duì)每個(gè)點(diǎn)找到覆蓋它的最上面的圓。
根據(jù)性質(zhì)4，最多取2(n-1)
2個(gè)點(diǎn)。對(duì)每個(gè)點(diǎn)找到覆蓋它的最上面的圓，需要O(n)次運(yùn)算?？倧?fù)雜度是O(n
3)。
其實(shí)此算法還有冗余，有些內(nèi)部小圓弧可以不用考慮，但是我沒想出怎么優(yōu)化。有誰知道更好的算法，請(qǐng)聯(lián)系我。blog留言或者qq交談或者發(fā)郵件都可以。
/**//*************************************************************************
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;
}