在 C 中使用数组而不是向量

Question

程序应该找到两点的最小外接圆。

示例： (1,1) (2,2)

这两个点的最小圆应该是圆心（1.5, 1,5）和半径 0.71 的圆。这只是图表上的表示： Two points inside a circle

问题解决方法如下：

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
const double INF = 1e18;
struct Point {
    double X, Y;
};
struct Circle {
    Point C;
    double R;
};
double dist(const Point& a, const Point& b)
{ return sqrt(pow(a.X - b.X, 2) + pow(a.Y - b.Y, 2)); }

int is_inside(const Circle& c, const Point& p)
{ return dist(c.C, p) <= c.R; }

Circle circle_from(const Point& A, const Point& B)
{
    Point C = { (A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 };
    return { C, dist(A, B) / 2.0 };
}

int is_valid_circle(const Circle& c, const vector<Point>& P)
{
    for (const Point& p : P)
        if (!is_inside(c, p)) return 0;
    return 1;
}

Circle minimum_enclosing_circle(const vector<Point>& P)
{
    int n = (int)P.size();
    if (n == 0)
        return { { 0, 0 }, 0 };
    if (n == 1)
        return { P[0], 0 };
    Circle mec = { { 0, 0 }, INF };
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            Circle tmp = circle_from(P[i], P[j]);
            if (tmp.R < mec.R && is_valid_circle(tmp, P))
                mec = tmp;
        }
    }
    return mec;
}
int main() {
  Circle mec = minimum_enclosing_circle({
      {1, 1},
      {2, 2},
  });
  printf("(%.2f,%.2f) %.2f", mec.C.X, mec.C.Y, mec.R);
  return 0;
}
int main() {
  Circle mec = minimum_enclosing_circle({
      {1, 1},
      {2, 2},
  });
  printf("(%.2f,%.2f) %.2f", mec.C.X, mec.C.Y, mec.R);
  return 0;
}

此代码的问题在于使用向量进行计算。如何在不使用向量和使用 C 数组的情况下编写此代码？

Answer 1

c 中的普通数组没有像 size() 这样的方法，在您的代码中您需要使用指针而不是 vector::size() 传递大小参数，并且 -> 它可以很好地工作

int is_valid_circle(const Circle c, const Point* P, size_t size)
{
    for(int i = 0; i < size ; i++)
    {
        if (!is_inside(c, P[i])) return 0;
    }

    return 1;
}

Circle minimum_enclosing_circle(const Point* P, size_t size)
{
    int n = size;
    if (n == 0)
        return { { 0, 0 }, 0 };
    if (n == 1)
        return { P[0], 0 };
    Circle mec = { { 0, 0 }, INF };
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            Circle tmp = circle_from(P[i], P[j]);
            if (tmp.R < mec.R && is_valid_circle(tmp, P, size))
                mec = tmp;
        }
    }
    return mec;
}

测试时间：https://godbolt.org/z/xWTqfqxsn

在 C 中使用数组而不是向量

Using arrays instead of vectors in C

c

c++

arrays

struct

vector