SSブログ

AOJ 0090: Overlaps of Seals

苦労しました...
この問題は、随分前から様々なアルゴリズムを考えていましたが、漸く通すことが出来ました...
"シールの重なり"と捉えるとなかなか難しい所がありますね.
#include <stdio.h>
#include <math.h>
#define SQ(x) ((x) * (x))
#define EPS 1e-5
typedef struct {
    double x;
    double y;
} POINT;

int dist(POINT a, POINT b, double d)
{
    if (sqrt(SQ(a.x - b.x) + SQ(a.y - b.y)) - d > EPS){
        return (0);
    }
    return (1);
}

int max(int a, int b)
{
    if (a > b){
        return (a);
    }
    return (b);
}

int main(void)
{
    POINT seal[100], v;
    static POINT l[300000];
    int s;
    double a, a0, d, t;
    int n;
    int count, ans;
    int i, j, k;
    
    while (1){
        scanf("%d", &n);
        
        if (!n){
            break;
        }
        
        for (i = 0; i < n; i++){
            scanf("%lf%*c%lf", &seal[i].x, &seal[i].y);
        }
        
        s = 0;
        
        for (i = 0; i < n; i++){
            for (j = 0; j < n; j++){
                if (dist(seal[i], seal[j], 2) && i != j){
                    //2つの円の交点を求める(一番苦労しました)
                    d = sqrt(SQ(seal[i].x - seal[j].x) + SQ(seal[i].y - seal[j].y));
                    a = atan2(seal[j].y - seal[i].y, seal[j].x - seal[i].x);
                    a0 = acos(0.5 * d);
                    
                    l[s].x = seal[i].x + cos(a0 + a);
                    l[s].y = seal[i].y + sin(a0 + a);
                    s++;
                    l[s].x = seal[i].x + cos(a0 - a);
                    l[s].y = seal[i].y + sin(a0 - a);
                    s++;
                }
            }
        }
                    
        ans = 1;
        for (i = 0; i < s; i++){
            count = 0;
            for (j = 0; j < n; j++){
                if (dist(seal[j], l[i], 1)){
                    count++;
                }
            }
            ans = max(ans, count);
        }
        
        printf("%d\n", ans);
    }
    
    return (0);
}

nice!(0)  コメント(0)  トラックバック(0) 

nice! 0

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

トラックバック 0

2006年JOI予選模擬4AOJ 0503: Cup ブログトップ

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。