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)?
Oczywiście użyłem scanf i printf, inaczej bym nie zawracał gitary. a cały kod wygląda mniej więcej tak:
scanf (abcd);
prinf (coś tam pomnóż coś tam podziel ewentualnie spierwiastkuj) ;
Więc nie wiem co tu można bardziej zoptymalizować… Dodam że skrócić w żaden sposób obliczeń się nie da.
@manjaro
scanf
i printf
to nie jest jeszcze (bardzo) szybki I/O, a jeżeli testów jest w przybliżeniu tak gdzieś “w ciul” (5*10^5) to może to mieć znaczenie.
Dlaczego amount jest typu long long?
Czy wiesz jakie/ile będzie miał x oraz y:
double x = 11 / 2
int b = 10000, d = 100;
double y = d * b * b
kodu
Jeżeli nie jesteś pewny, to napisz odpowwiedni programik
PS
Po uwzględnieniu powyższego i poprawieniu twojego kodu, uzyskałem TLE. Po przyśpieszeniu, a o tym jak, pisałem Ci w poprzednim wątku, pojawiło się zielone AC
PS 2
To było pytanie retoryczne. Użyty tu typ nie ma żadnego znaczenia do zaliczenia lub nie, zadania. Pytanie było retoryczne, bo znam odpowiedź. Nie ogarniasz typów zmiennych i to pytanie miało tylko zwrócić twoją uwagę na konieczność odrobienia tej zalegości lub jak tego nie odrobisz/nadrobisz będziesz ciągle miał z tym problemy.
Kluczem tutaj jest znajomość niejawnej konwersji typów [pytanie o x i y] w C++ oraz potem przyśpieszenie kodu.
I tu na forum, i w necie jest pełno informacji na temat szybszego wczytywania, chociażby np: https://www.geeksforgeeks.org/fast-io-for-competitive-programming/7
Twoje przeróbki kodu bardzo spowalniają jego działanie. Dlaczego sądzisz, że pow (a, 2) jest szybsze od a * a? Nie, nie jest. Takie użycie typów, jak to zrobiłeś w swoim kodzie, chociaż da Ci koniec końców AC, ale jest dalekie od optymalnego.