Maximum Winter-Contest 2011 B: Who Fired

keyword

平面幾何　C++

問題概要

2次元平面上に、M(<1000)個の点とN(<1000)個の円が与えられる。M個の点が全て周上にあるような円の中心を含む円がいくつあるか求める問題。

解法

M=1, M=2の場合はコーナーケースなので分けて解く(簡単なので略)。M>=3のときは、3点あれば円が決定できる(or円が無いことがわかる)ので後はやるだけ。もしかしたら入力には同じ点が与えられているのかもしれない。

const int MAX = 1009;

typedef complex<double> point;
point tmps[MAX];
vector<point> Ms;
pair<point, double> Cs[MAX];
vector<int> ans;
int N, M;

void print(){
    if(ans.empty()){
        puts("-1");
    }
    for(int i=0; i<ans.size(); i++){
        printf("%d%c",ans[i]+1, i+1==ans.size()?'\n':' ');
    }
}

void init(){
    for(int i=0; i<M; i++){
        bool ok = true;
        for(int j=i+1; j<M; j++)if(abs(tmps[i]-tmps[j])<EPS) ok = false;
        if(ok) Ms.push_back( tmps[i] );
    }
    M = Ms.size();
}

double oprod(point p1, point p2){
    return (p1.real()*p2.imag()) - (p1.imag()*p2.real());
}

double dist(point p1, point p2, point q){
    if(abs(p2-p1) < EPS) return 1e20;
    return fabs( oprod(p2-p1,q-p1) ) / abs(p2-p1);
}

void subsolve(){
    point p1, p2, t, v;
    t = (Ms[0] + Ms[1])*0.5;
    v = t - Ms[0];
    p1 = t + v*polar(1.0,0.5*PI);
    p2 = t + v*polar(1.0,-0.5*PI);
    for(int i=0; i<N; i++){
        double dis = dist(p1,p2,Cs[i].first);
        if(dis < Cs[i].second + EPS)ans.push_back(i);
    }
}

void solve(){
    init();
    if(M==1){
        for(int i=0; i<N; i++){
            ans.push_back(i);
        }
        return ;
    }
    if(M==2){
        subsolve();
        return ;
    }
    random_shuffle(ALL(Ms));
    point p1, p2, q1, q2, t, v;
    t = (Ms[0] + Ms[1])*0.5;
    v = t - Ms[0];
    p1 = t + v*polar(1.0,0.5*PI);
    p2 = t + v*polar(1.0,-0.5*PI);
    t = (Ms[2] + Ms[1])*0.5;
    v = t - Ms[1];
    q1 = t + v*polar(1.0,0.5*PI);
    q2 = t + v*polar(1.0,-0.5*PI);

    double dd = oprod(q2-q1, p2-p1);
    if(fabs(dd) < EPS){
        return ;
    }
    point center = p1 + (oprod(q2-q1,q1-p1)/dd*(p2-p1));
    double r = abs(center - Ms[0]);
    for(int i=0; i<M; i++){
        if(fabs(abs(center - Ms[i]) - r) > EPS){
            return ;
        }
    }
    for(int i=0; i<N; i++){
        if(abs(center - Cs[i].first) < Cs[i].second + EPS){
            ans.push_back(i);
        }
    }
}

int main(){
    while(scanf("%d%d ",&N,&M)){
        if(!N && !M) break;
        ans.clear();
        Ms.clear();
        for(int i=0; i<M; i++){
            double x, y;
            scanf("%lf%lf",&x,&y);
            tmps[i] = point(x,y);
        }
        for(int i=0; i<N; i++){
            double x, y, r;
            scanf("%lf%lf%lf",&x,&y,&r);
            Cs[i] = MP( point(x,y), r );
        }
        solve();
        print();
    }
    return 0;
}