Геометрические расчеты, поиск пути ⇐ JAVA

[Anonymous]

В прямоугольнике длиной 2a и шириной a вырежьте n непересекающихся кругов радиусом r=1 и найдите минимальное значение a.
Требования и цели:
Поместите n кругов радиуса 1 без перекрытия в двумерную прямоугольную область с соотношением сторон 2:1. Разработайте алгоритм с минимально возможной временной сложностью, чтобы найти минимальное значение (оптимальное или приблизительно оптимальное) прямоугольного диапазона. Требуется уметь находить ширину an прямоугольника с n в диапазоне [1,100]
Согласно требованиям темы, выполнить построение и анализ алгоритма, завершить программу компиляцию и предоставить конкретные тестовые примеры и результаты тестов.
Ниже показано мое решение с использованием Java. Основная идея – шестиугольное расположение. Я не знаю, правильно ли это. Надеюсь, кто-нибудь поможет мне это проверить.

Код: Выделить всё

import java.util.*;

публичный класс CirclePacking {

Код: Выделить всё

private static final double RADIUS = 1.0;

private static boolean canPlaceCircles(int n, double a) {
double width = 2 * a;
double height = a;

int rows = 1;
int circlesInRow = 0;

while (n > 0) {
if (rows % 2 != 0) {

circlesInRow = (int) (width  / (2 * RADIUS));
} else {

circlesInRow = (int) ((width - RADIUS) / (2 * RADIUS));
}
n -= circlesInRow;

if (rows == 1) {
height -= 2 * RADIUS;
} else {
height -= Math.sqrt(3) * RADIUS;
}

if (height < 0) {
return false;
}
rows++;
}

return true;
}

public static double findMinimumWidth(int n) {
double left = 1.0;
double right = n * 2.0;

while (right - left > 1e-6) {
double mid = (left + right) / 2;
if (canPlaceCircles(n, mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of circles: ");
int n = scanner.nextInt();
long startTime = System.nanoTime();
double minimumWidth = findMinimumWidth(n);
long endTime = System.nanoTime();
System.out.println("The minimum width a is: " + minimumWidth);
System.out.println(endTime-startTime);
}

Подробнее здесь: https://stackoverflow.com/questions/792 ... ath-search