0

问题：

许多交通锥已放置在圆形跑道上，以形成障碍物。您被要求确定可以在路线上行驶的最大尺寸的汽车。为简单起见，假设圆锥的宽度为零，并且汽车是完美的圆形且可无限机动。轨道本身是两个同心圆之间的区域。

形式上，如果在轨道中心周围存在一个位于形成轨道的圆之间的闭环，并且该环上的每个点距每个圆锥至少 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）。您的算法会错误地将直径计算为这些点之间的距离。然而，实际直径可能接近圆形轨道的宽度。你必须考虑点的全局结构来解决这个问题。

编辑：汽车采取的任何轨迹都将点和圆圈分成两组：出现在左侧的那些和出现在右侧的那些。请注意，内圈始终位于左侧，而外圈始终位于右侧。令两个集合之间的距离是属于它们的任意两个点之间的最小距离。然后你必须找到这些点的一个分区（其中左右圆圈属于不同的部分），以最大化它的两个部分之间的距离。这样的划分可以通过计算点和圆的最小生成树并在树中找到将左圆与右圆分开的最大边来获得。

于 2012-09-21T12:27:36.053 回答