c - 最大直径小车可操纵

Question

问题:

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

正式地，如果在形成轨道的圆之间存在一个围绕轨道中心的闭合环，并且环上的每个点都至少距离 c 距离，则可以由半径为 c 的汽车导航轨道的每个锥体和每个边界。

我的方法:

找出每对点之间的距离，然后为集合中的每个点找到同一集合中离它最近的点。让第 i 个点的距离为 dist[i] 并将 dist[i] 与 max((inner_radius-dist),(outer_radius-dist)) 进行比较 小者就是汽车的半径。

我编写了这个逻辑，但得到了错误的答案。我不确定我的算法是否正确。有人可以验证或建议更好的算法。

[EDIT] 以下是 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;
}

Answer 1

您的算法不正确。考虑一个只有两个彼此非常接近的锥体的测试用例(它们的距离几乎为 0)。您的算法会错误地将直径计算为这些点之间的距离。然而，实际直径可能接近圆形轨道的宽度。你必须考虑点的全局结构来解决这个问题。

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