0

質問：

障害物コースを形成するために、円形の競馬場に多数のトラフィック コーンが配置されています。コースをナビゲートできる最大サイズの車を決定するよう求められます。簡単にするために、コーンの幅は 0 で、車は完全な円形であり、無限に操縦可能であると想定されています。トラック自体は、2 つの同心円の間の領域です。

正式には、トラックを形成する円の間にあるトラックの中心の周りに閉じたループが存在し、ループ上のすべてのポイントが各コーンから少なくとも c の距離にある場合、半径 c の車でコースをナビゲートできます。トラックの各境界。

私のアプローチ:

ポイントのすべてのペア間の距離を見つけてから、セット内の各ポイントについて、同じセット内でそれに最も近いポイントを見つけます。この距離dist[i]を i 番目の点とし、 と比較dist[i]してmax((inner_radius-dist),(outer_radius-dist))、いずれか小さい方を車の半径とします。

このロジックをコーディングしましたが、間違った答えが返ってきました。私のアルゴリズムが正しいかどうかはわかりません。誰かがより良いアルゴリズムを検証または提案してください。

[編集] 以下はコードですc++ c

#include <stdio.h>
#include <math.h>

#define TEST_SIZE 500

/* This code is plain C so no need for this line:
using namespace std; */

int main(void) {
    int testCases, n;
    float x[TEST_SIZE], y[TEST_SIZE];//x[i], y[i] constitute pair (x,y) for ith point
    float distance, dist, min, r, R,radius;
    scanf("%d", &testCases);
    while ( testCases-- ) {
        scanf("%f%f%d", &r,&R, &n);
        //printf("r: %f, R: %f, n: %d\n", r, R, n);
        for (int i=0; i<n ; i++) {
            scanf("%f%f", &x[i], &y[i]);
        }
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                if (j!=i) {
                    dist = ((x[i]-x[j])*(x[i]-x[j])) + ((y[i]-y[j])*(y[i]-y[j]));// rhs of this equation is square of distance between 2 points
                    if(j==0 || dist>min) {
                        min=dist;
                    }
                //  printf("dist: %f\n", dist);
                }
            }
            min=sqrt(min);
            radius=sqrt((x[i]*x[i]) + (y[i]*y[i]));
            if(radius-r > R-radius) {
                if(min>radius-r) {
                min=radius-r;
                }
            } else {
                if(min>R-radius) {
                    min=R-radius;
                }
            }
            if(i==0 || distance>min) { 
                distance = min;
            }
        }
                    distance = floorf(distance*1000 + .5)/1000;
        //printf("distance: %f\n", distance);
        printf ("%f\n", distance);
    }
    return 0;
}
4

1 に答える 1

1

あなたのアルゴリズムは正しくありません。互いに非常に接近している (距離がほぼ 0 である) 2 つのコーンのみを含むテスト ケースを考えてみましょう。あなたのアルゴリズムは、これらの点の間の距離になるように直径を誤って計算します。ただし、実際の直径は円形トラックの幅に近い可能性があります。この問題を解決するには、点の全体構造を考慮する必要があります。

編集: 車が撮影したトラックは、点と円を 2 つのセットに分割します: 左側に表示されるものと右側に表示されるものです。内側の円は常に左側にあり、外側の円は常に右側にあることに注意してください。2 つのセット間の距離を、それらに属する任意の 2 点間の最小距離とします。次に、2 つの部分の間の距離を最大化するこれらの点 (左右の円が異なる部分に属する) の分割を見つける必要があります。このような分割は、点と円の最小スパニング ツリーを計算し、ツリー内で左の円を右の円から分離する最大のエッジを見つけることによって取得できます。

于 2012-09-21T12:27:36.053 に答える