3111 - Hotar

Cerinţa

Proprietatea trebuie împărțită fraților în mod egal. Zona are forma unui poligon convex cu vârfurile numerotate începând cu 1. Hotarul trebuie să fie un segment care are unul dintre capete în vârful 1 al poligonului. Trebuie să determinați celălalt capăt al segmentului care stabilește hotarul, așa încât ariile celor două suprafețe formate să fie egale. Punctul determinat trebuie să se afle pe poligon.

Date de intrare

Fișierul de intrare hotar.in conține pe prima linie numărul de vârfuri ale poligonului, notat cu n. Pe fiecare dintre următoarele n linii se află coordonatele vârfurilor, date în ordine trigonometrică (invers acelor de ceasornic), mai întâi ordonata, apoi abscisa, separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire hotar.out mai întâi abscisa, apoi ordonata pentru punctul calculat. Aceste două valori se scriu trunchiate la primele trei zecimale și se separă printr-un spațiu.

Restricţii şi precizări

3 ≤ n ≤ 15 Coordonatele vârfurilor sunt numere întregi cuprinse între -50 și 50 Pentru 30% din punctaj, punctul de afișat este unul dintre vârfurile poligonului; Pentru 60% din punctaj, punctul de afișat are coordonatele numere întregi; Nu există trei puncte coliniare pe conturul poligonului dat; Valorile de la ieșire se scriu cu exact trei zecimale, de exemplu, dacă ar trebui afișat 3 4.231867, se va scrie în fișier 3.000 4.231

Exemplu

hotar.in

3
0 0
1 0
0 1

hotar.out

0.500 0.500

Rezolvare

def read_input(filename):
    with open(filename, 'r') as file:
        n = int(file.readline().strip())
        vertices = [tuple(map(float, file.readline().split())) for _ in range(n)]
    return n, vertices

def calculate_area(vertices):
    area = 0
    n = len(vertices)
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i + 1) % n]
        area += x1 * y2 - x2 * y1
    return abs(area) / 2

def find_equal_areas(n, vertices):
    total_area = calculate_area(vertices)
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[(i + 1) % n]
        x3, y3 = vertices[(i + 2) % n]
        area1 = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2
        area2 = total_area - area1
        if abs(area1 - area2) < 1e-6:  # Verificăm egalitatea ariilor cu o toleranță mică
            return (x2 + x3) / 2, (y2 + y3) / 2  # Returnăm coordonatele celui de-al doilea vârf
    return None

def write_output(filename, result):
    with open(filename, 'w') as file:
        file.write("{:.3f} {:.3f}\n".format(*result))

def main():
    n, vertices = read_input('hotar.in')
    result = find_equal_areas(n, vertices)
    write_output('hotar.out', result)

if __name__ == "__main__":
    main()