UVa 10353 Circles in Hexagon

给定 $N$ 组测试数据，每组数据包含一个浮点数 $r$，表示圆的半径。需要计算一个正六边形的最小可能边长，使得该六边形能够恰好容纳 $5$ 个和 $8$ 个半径为 $r$ 的圆，且圆与圆之间、圆与六边形边界之间互不重叠。

输出时，对于每个 $r$，需要输出两个浮点数，分别对应能容纳 $5$ 个圆的最小边长和能容纳 $8$ 个圆的最小边长，结果保留小数点后 $12$ 位。

输入格式

第一行一个整数 $N$ $(0<N\le 10000)$，表示测试数据组数。

接下来 $N$ 行，每行一个浮点数 $r$。

输出格式

对于每组数据，输出一行两个浮点数，分别表示 $5$ 个圆和 $8$ 个圆对应的最小六边形边长。

样例输入

2
0.000000001
0.000000002

样例输出

0.00000000300 0.00000000371
0.00000000600 0.00000000742

题目分析

本题是一个几何优化问题，要求计算在正六边形中放置指定数量等半径圆时的最小六边形边长。由于没有简单的闭式解，我们需要通过几何分析和数值方法求解。

关键几何特性

解题思路

由于无法直接推导出边长 $a$ 关于半径 $r$ 的显式公式，我们采用数值方法求解：

算法步骤

时间复杂度

• 预处理：二分搜索 $O(\log (\frac{hi-lo}{EPS}))$，常数时间
• 主循环：$O(N)$
• 总复杂度：$O(N)$，完全满足题目要求（$N\le 10000$）

空间复杂度

• $O(1)$，仅使用常数个变量

代码实现

// Circles in Hexagon
// UVa ID: 10353
// Verdict: Accepted
// Submission Date: 2026-01-21
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include<bits/stdc++.h>
#define EPS 1e-14
using namespace std;

class Point {
public:
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator – (const Point &p) const { return Point(x – p.x, y – p.y); }
};

// 计算向量叉积（有向面积的两倍）
double cross(const Point &a, const Point &b, const Point &c) {
Point ab = b – a;
Point ac = c – a;
return ab.x * ac.y – ab.y * ac.x;
}

int main() {
int t;
const double PI = acos(–1.0);
const double SIN60 = sin(PI / 3.0);
const double COS60 = cos(PI / 3.0);

double r = 1.0; // 固定半径计算比例系数

// ———- 计算5个圆的比例系数 ———-
double lo5 = (2 * r) / SIN60;
double hi5 = (4 * r) / SIN60;

while (hi5 – lo5 > EPS) {
double a = (lo5 + hi5) * 0.5;
double x1 = r / SIN60;
double y1 = 0;
double y2 = a * SIN60 – r;

// 计算圆心1和圆心2之间的水平距离
double d = 4 * r * r – (y1 – y2) * (y1 – y2);
if (d < 0) { hi5 = a; continue; }
double x2 = sqrt(d) + x1;

double y3 = r;
d = 4 * r * r – (y3 – y2) * (y3 – y2);
double x3 = sqrt(d) + x2;

// 检查最右侧圆是否在六边形边界内
double area = cross(Point(a * COS60 + a, a * SIN60),
Point(2 * a * COS60 + a, 0),
Point(x3, y3));
if (area >= 0) { lo5 = a; continue; }

// 计算点到直线的距离
double dist = –area / a;
if (dist < r) lo5 = a;
else hi5 = a;
}

// ———- 计算8个圆的比例系数 ———-
double lo8 = (2 * r) / SIN60;
double hi8 = (4 * r) / SIN60;

while (hi8 – lo8 > EPS) {
double a = (lo8 + hi8) * 0.5;
double x1 = r / SIN60;
double y1 = 0;
double x2 = x1 + 2 * r * COS60;
double y2 = 2 * r * SIN60;
double y3 = a * SIN60 – r;

// 计算圆心2和圆心3之间的水平距离
double d = 4 * r * r – (y2 – y3) * (y2 – y3);
if (d < 0) { hi8 = a; continue; }
double x3 = sqrt(d) + x2;

double y4 = r;
d = 4 * r * r – (y4 – y3) * (y4 – y3);
double x4 = sqrt(d) + x3;

// 检查最右侧圆是否在六边形边界内
double area = cross(Point(a * COS60 + a, a * SIN60),
Point(2 * a * COS60 + a, 0),
Point(x4, y4));
if (area >= 0) { lo8 = a; continue; }

// 计算点到直线的距离
double dist = –area / a;
if (dist < r) lo8 = a;
else hi8 = a;
}

// ———- 处理输入输出 ———-
scanf("%d", &t);
while (t—) {
scanf("%lf", &r);
printf("%.12lf %.12lf\\n", lo5 * r, lo8 * r);
}

return 0;
}

总结

本题通过几何分析和数值方法相结合的方式，解决了正六边形中放置等半径圆的最小边长问题。主要技巧包括：

该算法高效可靠，时间复杂度 $O(N)$，完全满足题目要求。在实际编程竞赛中，这种几何数值方法常用于解决没有闭式解的优化问题。