FR_06_06 - Bajtek i trójkąt

Potwierdzam

Nie wiem czy powinienem to pisać, ale zapoznaj się z twierdzeniem Stewarta.

Wszystkie podane wyżej wejścia/wyjścia są ok.

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)?

mam wrażenie, że twój program rozwiązuje inny problem, niż podano w zadaniu - i daje poprawne wyniki tylko dla pewnych trójkątów

sprawdź dla takich danych testowych:

2
13 20 7 4
20 13 4 7

Dzięki za test. Przyczyną błędu były niedokładne rysunki (nie mając nawet linijki za bardzo skupiłem się na algebrze, a za mało na rysunkach trójkątów i wciąż miałem w wyobraźni coś plus minus równobocznego). Obserwacje są prawdziwe jedynie dla części trójkątów, ale nie dla wszystkich.

Niech mi ktoś powie jakim cudem w algorytmie który polega na wczytaniu, prostym przeliczeniu i wyświetleniu wyniku mam czas 1.19s a rekordzista ma 0.2s? Jakim cudem mój kod jest sześć razy wolniejszy skoro używamy tego samego języka a kod jest maksymalnie uproszczony?

Jeżeli ja mam dla bardzo prostego kodu (obliczenia w 3 liniach) 4.50 s to wniosek jest jasny:

optymalizacja mojego kodu < optymalizacja Twojego kodu < optymalizacja kodu rekordzisty

Szybkie IO ? Czesto sama zamiana cin/cout na scanf/printf dużo daje. A może i jeszcze jakaś optymalizacja

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.

Witam, jest w stanie ktoś wskazać błąd, wszystkie testy przechodzą podane w tym temacie, nie wiem gdzie jest błąd a sędzia odrzuca, używam twierdzenia stewarta,

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.

Racja z tymi zmiennymi, biorę to pod uwagę, przerobiłem trochę kod i tez jest TLE, ale jak to zooptymalizowac to nie mam pojęcia

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.