Boş Üçbucaqlar
Çox sadə bir problemi çox çətin bir hala gətirməyin nə qədər asan olduğunu bilirsinizmi? Budur bir nümunə. Təyyarədə N düz xətt ilə neçə üçbucaq düzəldə bilərsiniz? Fərqli meyllərə malik olduqları və heç biri eyni nöqtədə kəsişmədiyi müddətcə üçbucaqlar olacaq və bu, əldə edə biləcəyiniz maksimum sayıdır.
Yaxşı, bu o qədər də pis deyildi. Amma gəlin görək yalnız boş üçbucaqları (yəni, heç bir xətt üçbucağın içindən keçməyən) saydığımızda nə baş verir. O zaman üçbucaqların sayı birdən çox azalır. Məsələn, 4 düz xətt ilə yalnız 2 boş üçbucaq düzəldə bilərik, halbuki üçbucaqların ümumi sayı 4 qədər ola bilər. Diaqrama baxın.
Əslində, N xətt ilə çəkilə bilən maksimum boş üçbucaqların ümumi formulu məlum deyil. Lakin çətin olan xəttlərin düzgün konfiqurasiyasını tapmaqdır. Sizin işiniz çox daha asandır; təyyarədə verilmiş N düz xətt ilə boş üçbucaqların sayını hesablayın.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər bir test halı təyyarədəki xəttlərin sayını göstərən bir tam ədəd N, 1 ≤ N ≤ 500 olan bir sətir ilə başlayır. Növbəti N sətir hər biri (x_1, y_1) və (x_2, y_2) nöqtələrindən keçən bir düz xətti təmsil edən dörd tam ədəd x_1, y_1, x_2 və y_2 (arasında −1000 və 1000) ehtiva edir. Heç bir üç xəttin eyni nöqtədə kəsişmədiyi və bütün xəttlərin fərqli olduğu təmin edilir. Giriş N = 0 olan bir sətir ilə bitir.
Çıxış
Hər bir test halı üçün verilmiş xətlər tərəfindən yaradılan boş üçbucaqların sayını ehtiva edən bir sətir çap edin.