Minimalny całkowity obwód prostokąta przy zadanym całkowitym polu

Witam
Piszę funkcję, której zadaniem jest znalezienie minimalnego obwodu prostokąta przy danym polu. Kod poniżej.

typedef unsigned long long ull;

ull minimum_perimeter(ull area) {
  double a,b;
  for(a = floor(sqrt(area)),b = ceil(sqrt(area));a*b!=area;a--)
  {
    ull b_b=b;
    for(;a*b_b<area;b_b++);
    if(a*b_b==area)
      return 2*(a+b_b);
  }
  return 2*(a+b);
}

Niestety program nie przechodzi mi testów z powodu przekroczenia czasu wykonania.
1 <= area <= 5 x 10 ^ 10
taką wartość może przyjąc parametr area.
Mógłby ktoś podpowiedzieć, jak poprawić kod.

Mógłby ktoś podpowiedzieć, jak poprawić kod.

Pomyśleć chwilę nad tym, ile to wynosi. Tak matematycznie. Nie potrzebujesz żadnej pętli ani zgadywania. Wyznacz na kartce papieru wzór, po czym go zaprogramuj. Złożoność O(1).

Podpowiedź: im bardziej coś okrągłe, tym mniejsze.
Podpowiedź2: kwadrat to najbardziej okrągły prostokąt.

Daj pełną treść zadania (link do zdania), bo przy treści problem jest tak naprawdę problemem faktoryzacji wartości pola.
Najlepiej zacząć od Metody Fermata bo najmniejszy obwód otrzymamy, gdy prostokat jesteś bliski kwadratowi.

To muszą być wartości, które dają prostokąt. Nie można tego zrobić wyciągając pierwiastek z area. Poniżej pełna treść zadania,.

A rectangle is can be defined by two factors: height and width.

Its area is defined as the multiplication of the two: height * width.

Its perimeter is the sum of its four edges: height + height + width + width.

It is possible to create rectangles of the same area but different perimeters. For example, given an area of 45, the possible heights, widths and resultant perimeters would be:

(1, 45) = 92

(9, 5) = 28

(15, 3) = 36

Note that (6, 7.5) has an area of 45 too, but is discarded in this kata because its width is non integral.

The task is to write a function that, given an area as a positive integer, returns the smallest perimeter possible of a rectangle with integral side lengths.

Input range:
1 <= area <= 5 x 10 ^ 10

@gonskabalbinka:

Jeśli masz zadanie w integereach, to dlaczego piszesz kod w double ?

BTW porównanie w double to rzadko się udaje

@gonskabalbinka: Obejrzyj to:

Film powyzej nie ma duzego sensu. Narysowowany pojedynczy przypadek i od razu wniosek ze to zawsze musi byc kwadrat. No ale gdyby zamiast 36 zostawil A, potem policzyl pochodna i zrobil z tego rownanie z 1 zmienna, to bez zadnego rysowania by latwo policzyl minimalny obwod (i jesli czegos nie pokrecilem to przypadkiem wniosek mu wyszedl prawdziwy).

Może nie do końca, wyglądam że na jego podstawie można zaimplementować takie rozwiązanie:
https://www.tutorialspoint.com/cplusplus-program-to-get-minimum-perimeter-of-rectangle-whose-area-is-n

Poniżej link do zadania
link

Podpowiedź:
Potrzebujesz złożoności pierwiastkowej, wystarczy że znajdziesz wszystkie dzielniki podanego pola i z nich musisz wywnioskować odpowiedź

Dzięki za odpowiedzi, ale dzisiaj już nie mam siły żeby rozwiązać to zadanie.

Rozkładasz powierzchnie na czynniki pierwsze:
np:

• 45=5*3*3
• 30=5*3*2
• 81=3*3*3*3
• 89=89
  Po czym znajdujemy taki podział aby iloczyn był jak najbliżej połowy, np:
  45=(5)*(3*3) => obwód (5+9)*2 = 28
30=(5)*(3*2) => obwód (5+6)*2 = 22
81=(3*3)*(3*3) => obwód (9+9)*2 = 36
89=(89)*1 => obwód (89+1)*2 = 180
  Niestety jedynie brutal-force z heurystyką iloczyn<=powierzchnia

Może nie rozumiem do końca trudności zadania, ale czy to nie będzie po prostu sqrt(area) * 4?

Nawet sprawdziłem i faktycznie tak wychodzi (kod w JS, ale temat wydaje się bardziej pod matmę i algorytmy, a nie specyficzny dla C++). Jak obliczam różne wartości boków po kolei, to i tak wychodzi mi ta liczba, którą wcześniej wyliczyłem jako Math.sqrt(area) * 4

const area = 1234;
const predicted = Math.sqrt(area) * 4;
console.log("Area=", area);
console.log("Predicted perimeter", predicted);

const step = 0.001;
let minPerimeter = Infinity;

for (let w = step; w <= area / step; w += step) {
	const h = area / w;
	const perimeter = 2 * (w + h);
	if (perimeter < minPerimeter) {
		minPerimeter = perimeter;
	}
}
console.log("Computed perimeter", minPerimeter);	

Najszybciej (ale niekoniecznie optymalnie) można to zakodować tak:

#include <math.h>
typedef unsigned long long ull;


ull minimum_perimeter(ull area) {
  ull a = sqrt(area);
  ull b = area/a;
  while (a * b != area) {
    a--;
    b = area/a;
  }
  return 2*a + 2*b;
}

Wg mnie trochę prościej :P

#include <math.h>
typedef unsigned long long ull;

ull minimum_perimeter(ull area)
{
  ull w=sqrt(area);
  //while(w*(area/w)!=area) --w;
  while(area%w) --w;
  return 2*(w+area/w);
}

A minimalny obwód prostokąta przy zadanym polu, to nie jest zawsze kwadrat?