#!/usr/bin/python3

# V textovém řešení jsme opomíjeli jeden aspekt řešení, a to starost aby řešení
# počítalo přesně (tedy aby neporovnávalo na rovnost floaty nebo nepřesné
# výsledky goniometrických funkcí). Aby kód skutečně odpovídal správně není je
# nutné se v samotné implementaci těmto faktorům věnovat, což trošku
# znepřehledňuje samotný kód. Idea algoritmu je nicméně stále stejná jako v
# popisu algoritmu.

# V souvislosti s tímto je v kódu zaveden "základní popis úhlu". V našem
# algoritmu často pracujeme s úhly, které máme popsané dvojicí bodů A a B, daný
# úhel je pak úhel A0B (kde 0 je počátek). Velikost tohoto úhlu se pak dá
# vyjádřit (z kosinové věty) jako arccos((A^2+B^2-(A-B)^2)/2AB). Abychom se
# vyhnuli používání goniometrických funkcí, budeme si u úhlu pamatovat trojici
# (kvadrant, čitatel_zlomku_na_druhou, jmenovatel_zlomku_na_druhou), kde
# "kvadrant" určuje ve kterém z intervalů (0-90), (90-180), (180-270), (280-360)
# se úhel nachází. Navíc budeme uchovávat čitatel a jmenovatel v základním
# tvaru. Uvidíme, že tato trojice stačí na efektivní porovnávání úhlů bez
# použití nepřesných goniometrických funkcí, dělení a odmocnin

# Funkci pro spočítání nejmenšího společného násobku importuje ze standardní
# pythoní knihovny, pokud vás zajímá, jak se nejmenší společný násobek (angl.
# greates common divisor, zkráceně gcd), nahlédněte do naší kuchařky. Doplňme,
# že spočítání násobku má složitost O(log n)
# [https://ksp.mff.cuni.cz/kucharky/teorie-cisel/] nadpis "Euklidův algoritmus"
from fractions import gcd
from functools import cmp_to_key

# Je předvyplněno několik testů pro vaši představu. Chcete-li odkomentujte jiný
# nebo napište vlastní
vstup = [(1,1), (1,2)]
#vstup = [(0,0), (3,0), (2,1)]
#vstup = [(0,0), (1,0), (0,1)]
#vstup = [(0,1), (1,1), (1,0), (3,0), (2,2), (3,2), (2,3)]
#vstup = [(3,0), (4,0), (5,2), (5,3), (2,4), (1,4), (0,2), (0,1)]
#vstup = [(1,1), (2,2), (0,2), (0,1), (0,3), (-1,1), (-2,2), (-1,-1), (-2,-2),
#        (0,-1), (0,-2), (0,-3), (1,-1), (2,-2)]

def porovnej(x, y):
    # Jedná se o standardní implementaci "cmp" z Pythonu 2, pokud jste jejím
    # zápisem zmateni, netrapte se jejím luštěním. Tato funkce jednoduše vrací
    # 1 pokud x > y, -1 pokud x < y a 0 pokud se x a y rovnají
    return (x > y) - (x < y)

def znamenko(x):
    # Vrátí znaménko čísla, čili 0 pro 0, 1 pro kladná a -1 pro záporná čísla
    return porovnej(x, 0)

def vzdalenost_na_druhou(u, v = (0,0)):
    # Spočítá vzdálenost dvou bodů podle Pythagorovy věty, popř. délku vektoru
    # pokud je zadán pouze jeden vektor. Abychom se zbavili počítání s
    # odmocninami, vrací druhou mocninu vzdálenosti
    return (u[0] - v[0]) ** 2 + (u[1] - v[1]) ** 2

def determinant(u, v):
    # Vrací skalární součin dvou vektorů pro zjištění polohy bodu vůči přímce,
    # viz [https://ksp.mff.cuni.cz/kucharky/geometrie/]
    return u[0] * v[1] - u[1] * v[0]

def porovnej_uhly(a, b):
    # Porovná dva úhly v základním tvaru (popsaným výše). Nejprve zjistí jestli
    # se nedají jednoduše porovnat pomocí kvadrantů. Pokud ne porovnáme zlomky
    # jednotlivých úhlů. Tím, že budeme násobit čitatele jednoho zlomku se
    # jmenovatelem druhého dostaneme stejný výsledek bez použití nepřesného
    # dělení. Tento výsledek ještě musíme obrátit pokud pracujeme s úhlem
    # menším než 180 stupňů, jelikož je kosinus na tomto intervalu klesající,
    # tedy menší argument kosinu znamená větší celkový výsledek. A konečně jej
    # musíme ještě jednou obrátit pokud pracujeme s úhlem mezi 90 a 270 stupni
    # jelikož v tomto intervalu by měl vyjít čitatel záporný, ale jeho
    # umocněním na druhou jsme toto minus ztratili, dostali bychom tedy opačný
    # výsledek. Proto používáme opravu násobením -a[0][0] * a[0][1]
    return (
            porovnej(kvadrant_na_cislo(a[0]), kvadrant_na_cislo(b[0]))
            or -a[0][0] * a[0][1] * porovnej(a[1] * b[2], a[2] * b[1])
            )

def kvadrant_na_cislo(x):
    # Pro nás je často praktičtější pracovat s kvadranty ve formátu dvojice
    # (je_nad_osou_x, je_napravo_od_osy_y), tato funkce převádí tento formát na
    # klasický formát I., II., III., IV. kvadrant, který znáte ze střední školy,
    # navíc vrátí "poloviční" kvadrant pro případy, kdy se bod nachází na
    # hranici
    return {
            (0,1): 0,
            (1,1): 1,
            (1,0): 1.5,
            (1,-1): 2,
            (0,-1): 2.5,
            (-1,-1): 3,
            (-1,0): 3.5,
            (-1,1): 4,
            }[x]

def uhel_na_zakladni(x):
    # Vezme úhel zadaný dvojicí bodů a vrátí jeho zápis v základním formátu,
    # připomeňme, že základní tvar úhlu vychází z interpretace úhlu pomocí:
    # arccos((A^2+B^2-(A-B)^2)/2AB)
    # Daná trojice je pak
    # (kvadrant, čitatel_zlomku_na_druhou, jmenovatel_zlomku_na_druhou)
    # Zmíněný kvadrant zapisujeme dvojící (je_nad_osou_x, je_napravo_od_osy_y)

    a, b = x
    an = (a[1], -a[0])
    kvadrant = (znamenko(determinant(a, b)), znamenko(determinant(an, b)))
    kvadrant_cislo = kvadrant_na_cislo(kvadrant)

    delka_a_na_druhou = vzdalenost_na_druhou(a)
    delka_b_na_druhou = vzdalenost_na_druhou(b)
    delka_c_na_druhou = vzdalenost_na_druhou(a, b)

    citatel = delka_a_na_druhou + delka_b_na_druhou - delka_c_na_druhou

    citatel_na_druhou = citatel ** 2
    jmenovatel_na_druhou = 4 * delka_a_na_druhou * delka_b_na_druhou

    # Zlomek zapíšeme v základním tvaru pomocí dělení největším společným
    # dělitelem
    delitel = gcd(citatel_na_druhou, jmenovatel_na_druhou)
    return (kvadrant, citatel_na_druhou // delitel, jmenovatel_na_druhou // delitel)

def maximalni_delka_palindromu(string):
    # Jednoduchá funkce, která "najde" nejdelší palindrom ve slově. Jak jsme
    # slíbili na tuto podúlohu se podíváme v poslední sérii, takže zde je její
    # omezená varianta, která má přednastavené výsledky několika příkladů,
    # pokud narazí na nový příklad zeptá se uživatele na výsledek.
    # Na začátku zadaný řetězec zkonvertuje na skutečný "string", tato konverze
    # není nutná (navíc omezuje na 26 různých znaků), ale je vhodná pro
    # představu a hledání nejdelšího palindromu ručně.
    videne = {}
    videne_i = 0
    preklad = []
    for znak in string:
        if znak not in videne:
            videne[znak] = chr(videne_i + ord('a'))
            videne_i += 1
        preklad.append(videne[znak])
    preklad = ''.join(preklad)

    try:
        return {
                "abbbbabbbb": 7,
                "abbcddeffabbcddeff": 2,
                "abbcddcbbabbcddcbb": 15,
                "abbcddeffgffeddcbbahhabbcddeffgffeddcbbahh": 40,
                "abbcddeffgbbabbcddeffgbbabbcddeffgbbabbcddeffgbb": 5,
                "abccbdefggfedbccbabccbdefggfedbccbabccbdefggfedbccbabccbdefggfedbccb": 65,
                }[preklad]
    except KeyError:
        return int(input("Jaký je nejdelší palindrom v " + preklad + "? "))


if __name__ == "__main__":
    l = len(vstup)
    tx = sum([x for (x,_) in vstup]) # x-ová souřadnice těžiště vynásobená l
    ty = sum([y for (_,y) in vstup]) # y-ová souřadnice těžiště vynásobená l

    # Nové body dostaneme odečtením těžiště, navíc všechny souřadnice
    # přenásobíme l, abychom se vyhnuli dělení. Pokud existuje bod se
    # souřadnicemi 0,0 zahodíme ho (proto koncový if)
    nove_body = [(x * l - tx, y * l - ty) for x,y in vstup if x*l-tx or y*l-ty]

    # Pro každý bod spočítáme úhel s osou x (vektorem (1,0))
    uhly_bodu = {bod: uhel_na_zakladni(((1,0), bod)) for bod in nove_body}

    # Body setřídíme podle úhlu který mají, nemůžeme je porovnávat přímo, ale
    # musíme se nejprve podívat na příslušné úhly a ty úhly pak porovnat pomocí
    # "porovnej_uhly". Pokud jsou úhly stejné, musíme řadit dle vzdálenosti od
    # počátku. Celý příkaz by se v Pythonu 2 dal zapsat jako:
    # nove_body.sort(cmp=(lambda x, y: porovnej_uhly(...) or porovnej(...)))
    # pužití cmp_to_key je akorát "kouzelná formulka", která způsobí, aby se to
    # setřídilo stejně jako zmíněný sort v Pythonu 2, Python 3 totiž již
    # nepodporuje argument cmp
    nove_body.sort(key=cmp_to_key(
        lambda x, y: (
            porovnej_uhly(uhly_bodu[x], uhly_bodu[y])
            or porovnej(vzdalenost_na_druhou(x), vzdalenost_na_druhou(y))
            )
        ))

    retezec = [] # Dosavadní řetězec
    posledni_body = [] # Seznam řetězců se stejným úhlem
    for i in range(len(nove_body)):
        bod = nove_body[i]
        minuly_bod = nove_body[i-1]
        # Pokud jsme přešli na nový úhel...
        if not posledni_body or uhel_na_zakladni((minuly_bod, bod))[0][0]:
            # ... tak zkopírujeme převrácený příslušný seznam bodů
            retezec += reversed(posledni_body)
            # ... zapíšeme úhel
            retezec.append(uhel_na_zakladni((minuly_bod, bod)))
            # ... a přemažeme seznam úhlů se stejným úhlem
            posledni_body = []
        retezec.append(vzdalenost_na_druhou(bod))
        posledni_body.append(vzdalenost_na_druhou(bod))
    retezec += reversed(posledni_body)

    if maximalni_delka_palindromu(retezec + retezec) > len(retezec):
        print("Množina bodů JE osově souměrná")
    else:
        print("Množina bodů NENÍ osově souměrná")