Proszę o kontrprzykład albo inne wskazanie błędu logicznego.
Pole dowolnego trójkąta o bokach a, b, c:
sqrt(p * (p - a) * (p - b) * (p - c)), gdzie p = (a + b + c) / 2.
Czyli mając długości trzech odcinków zawsze wyznaczę pole trójkąta ograniczonego tymi odcinkami. Jednocześnie:
h = 2 * Pabcd / (d + c)
Obserwacja: wysokość h trójkąta o bokach a, b, c + d wyznacza trójkąty ADH i BCH, a niewiadomej długości odcinek x zawiera się w jednym z tych dwóch trójkątów albo jest wysokością trójkąta ABCD. Stosuję lekko niekonwencjonalne nazewnictwo trójkątów, za to najbardziej intuicyjne względem treści zadania (patrz: rysunek do przykładowego wejścia).
Łącząc wzór Herona z klasycznym wzorem na pole trójkąta (podstawa * wysokość opuszczona na tą podstawę / 2) uzyskuję cztery możliwe wyniki:
x1 = sqrt(d * d + a * a + 2 * sqrt(d * d * (a * a - h * h)))
x2 = sqrt(d * d + a * a - 2 * sqrt(d * d * (a * a - h * h)))
x3 = sqrt(c * c + b * b + 2 * sqrt(c * c * (b * b - h * h)))
x4 = sqrt(c * c + b * b - 2 * sqrt(c * c * (b * b - h * h)))
Obserwacja:
x = min(x1, x2, x3, x4)
Program napisany wg tego algorytmu otrzymał WA, natomiast zadziałał dla testów w tym temacie, testu przykładowego i testów mojego pomysłu. Prawdopodobnie ostatnia obserwacja, gdybym chciał ją udowodnić, okazałaby się błędna. Niemniej gdy na ok 40 różnych przypadków testowych 40 razy otrzymuję prawidłową odpowiedź, zastanawiam się, czy leży implementacja czy algorytm.
Co zaś się tyczy implementacji:
#include <bits/stdc++.h>
using namespace std;
double Heron(double a, double b, double c)
{
double p = (a + b + c) / 2;
return sqrt(p * (p - a) * (p - b) * (p - c));
}
int main()
{
int t;
double a, b, c, d;
double Pabcd, Padh, Pbch;
double h;
double wynik1, wynik2, wynik3, wynik4;
double wynik;
cin >> t;
while(t--) {
cin >> a >> b >> c >> d;
Pabcd = Heron(a, b, c + d);
h = 2 * Pabcd / (d + c);
// Padh = Heron(a, d, h);
// Pbch = Heron(b, c, h);
wynik1 = sqrt(d * d + a * a + 2 * sqrt(d * d * (a * a - h * h)));
wynik2 = sqrt(d * d + a * a - 2 * sqrt(d * d * (a * a - h * h)));
wynik3 = sqrt(c * c + b * b + 2 * sqrt(c * c * (b * b - h * h)));
wynik4 = sqrt(c * c + b * b - 2 * sqrt(c * c * (b * b - h * h)));
// cout << fixed << setprecision(2) << wynik1 << " " << wynik2 << " " << " " << wynik3 << " " << wynik4 << endl;
// cout << Pabcd << " " << Padh << " " << Pbch << endl;
// cout << Heron(a, d, wynik1) << " " << Heron(a, d, wynik2) << endl;
// cout << Heron(a, d, wynik3) << " " << Heron(a, d, wynik4) << endl;
wynik = min(wynik1, wynik2);
wynik = min(wynik, wynik3);
wynik = min(wynik, wynik4);
cout << fixed << setprecision(2) << wynik << endl;
}
return 0;
}
Komentarze zostawiam, jeżeli ktoś chce podejrzeć obliczenia pośrednie (może tam coś schrzaniłem)?
