題目描述：
在無限平面上有N(N<1,000)個(gè)圓。問一條直線最多可以“穿過”幾個(gè)圓，相切也算。
算法分析：
這樣的線一定是某兩個(gè)圓的切線。但是枚舉切線再O(N)判斷的話肯定會(huì)T。
于是我們枚舉每個(gè)“中心圓”，求出這個(gè)圓與其他所有圓的切線。并極角排序。
把每個(gè)切線想像成事件點(diǎn)，每個(gè)事件點(diǎn)要么增加一個(gè)圓，要么刪除一個(gè)圓。
這樣的話對(duì)這個(gè)環(huán)行區(qū)間進(jìn)行統(tǒng)計(jì)就可以了。
求切線的時(shí)候，要判斷中心圓與其他圓的關(guān)系： 包含，內(nèi)切or外切，相交，被包含，分離。
求切線其實(shí)只需要求一個(gè)角就可以了，不需要求完整的兩點(diǎn)式。
#include<iostream>
#include<cassert>
#include<algorithm>
#include<cstdio>
#include<complex>
#include<cmath>
using namespace std;
// template
typedef complex<
double> pnt;
typedef pair<pnt,
double> circle;
const int N = 1005;
const double eps = 1e-10;
const double pi = acos(-1.0);
inline
bool eq(
double a,
double b){
return abs(b-a) < eps;}
inline
double fix(
double arg) {
while(arg > pi) arg -= 2*pi;
while(arg <= -pi) arg += 2*pi;
return arg;
}
circle num[N];
struct line {
int id,c;
double arg;
line(){}
line(
int _id,
int _c,
double _arg) :
id(_id) , c(_c), arg(_arg){
// cout<<"add: "<<id<<" "<<arg<<" "<<c<<endl;
}
bool operator < (
const line& A)
const{
return eq(arg , A.arg) ? c > A.c : arg < A.arg;
}
} Line[N<<2];
// cut line
#define ht first
#define rs second
inline
void cut_line(
const circle &A,
const circle &B,
int& ans,
int& cnt,
const int& id) {
double d = abs(A.ht - B.ht) ;
if(d <= abs(A.rs - B.rs)) {
if(d <= B.rs - A.rs ) {ans ++;
return ;}
if(eq(d , A.rs - B.rs) ) {
Line[cnt++] = line(id, 1 , arg(B.ht - A.ht));
Line[cnt++] = line(id,-1 , arg(B.ht - A.ht));
}
return ;
}
double t;
t = acos((A.rs - B.rs)/ d);
double ag = arg(B.ht - A.ht);
Line[cnt++] = line(id, 1 , fix(ag-t));
Line[cnt++] = line(id,-1 , fix(ag+t));
if(d > A.rs + B.rs + eps) {
double t = acos((A.rs + B.rs)/d);
Line[cnt++] = line(id, 1 , fix(ag+t));
Line[cnt++] = line(id,-1 , fix(ag-t));
}
}
// solve
bool vis[N];
int work(
int n,
int len){
int ans = 0, sum = 0;
for(
int i=0;i<n;i++){
vis[i] = 0;
}
for(
int i=0;i<len+len;i++) {
int k = i%len;
int id = Line[k].id;
int c = Line[k].c;
if(c == 1){
assert(vis[id]==0);
vis[id] = 1; sum ++;
}
else if(c == -1) {
if(vis[id] == 1)
sum --, vis[id] = 0;
}
if(sum > ans ) ans = sum;
}
return ans;
}
// main
int main(){
int cas;
cin >> cas;
for(
int oo=1; oo<= cas; oo++) {
int n,len = 0;
scanf("%d",&n);
for(
int i=0;i<n;i++) {
int x,y,r;
scanf("%d%d%d",&x,&y,&r);
num[i] = make_pair(pnt(x,y) , r);
}
int ans = 0;
for(
int s = 0; s < n; s ++) {
// cout<<"start: "<<s<<endl;
len = 0;
int sum = 1;
for(
int i=0;i< n; i++)
if(i!=s)
cut_line(num[s] , num[i], sum, len, i);
sort(Line, Line + len);
sum += work(n,len);
if(sum > ans) ans = sum;
}
printf("Case #%d: %d\n",oo, ans);
}
}
posted on 2012-08-06 14:58
西月弦 閱讀(1260)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告