View source for 1246 - Dispozitiv

== Enunt ==
Specificul insulelor din arhipelagul Maldive (Oceanul Indian) este faptul că toate cele N insule ale sale au forma unui triunghi. Localizarea acestor insule folosește coordonatele carteziene ale celor trei vârfuri.

Administrația acestor insule dorește să instaleze un dispozitiv de emisie-recepţie pe apă sau pe o insulă, într-un punct având coordonate numere naturale (xD, yD), ce transmite semnale numai pe direcții orizontale și verticale concomitent, cu următoarele proprietăţi:

* notând cu NRO numărul de insule la care ajunge semnalul pe orizontală și cu NRV numărul de insule la care ajunge semnalul pe verticală, suma NRO + NRV trebuie să fie maximă;
* dacă există mai multe puncte cu proprietatea anterioară, atunci se va alege punctul cel mai mic în ordine lexicografică.
== Cerinţa ==
Să se scrie un program care cunoscând numărul de insule N şi coordonatele carteziene ale vârfurilor acestora, determină coordonatele xD și yD cu proprietățile din enunţ.
== Date de intrare ==
Fișierul de intrare dispozitiv.in conține pe prima linie numărul N, cu semnificaţia de mai sus, iar pe următoarele N linii se află câte şase numere reprezentând coordonatele vârfurilor insulelor (x1 y1 x2 y2 x3 y3).
== Date de ieșire ==
Fișierul de ieșire dispozitiv.out va conține pe prima linie coordonatele xD și yD cu proprietatea din enunţ, separate printr-un spațiu.
== Restricţii şi precizări ==
* propoziția va conține cel mult '''255''' de caractere;
* cuvintele conțin doar litere și/sau cifre și conțin cel mult '''20''' de caractere;
* dacă în propoziție există mai multe cuvinte palindrom de lungime maximă, se va afișa primul dintre ele;
* semnele de punctuație din propoziție pot fi ''':;.,'''
* nu se face distincție între literele mari și cele mici;
* pentru toate testele date există soluție
== Exemplul 1 ==
; dispozitiv.in

6
0 7 4 7 1 10
5 1 6 1 6 2
2 3 2 4 4 4
2 0 1 2 4 2
6 7 7 7 6 10
5 0 7 0 7 1

; dispozitiv.out

2 1
<br>

== Explicatie ==
Codificăm insulele cu 1, 2, …, 6, iar insula i va avea coordonatele vârfurilor pe linia i + 1.
Paralelele la axa Ox și Oy prin punctul de coordonate (2, 1) intersectează un număr de NRO = 3 triunghiuri și anume: 4, 2, 6 pe orizontală şi intersectează un număr de NRV = 3 triunghiuri: 4, 3, 1 pe verticală. NRO + NRV este maxim.
Mai sunt și alte puncte cu aceeași proprietate, dar mai mari în ordine lexicografică, cum ar fi punctul de coordonate (6, 1).
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(file_name):
    with open(file_name, 'r') as file:
        n = int(file.readline().strip())
        triangles = []
        for _ in range(n):
            coords = list(map(int, file.readline().strip().split()))
            triangles.append([(coords[i], coords[i+1]) for i in range(0, 6, 2)])
    return triangles

def write_output(file_name, xD, yD):
    with open(file_name, 'w') as file:
        file.write(f"{xD} {yD}\n")

def on_same_side(p1, p2, a, b):
    cp1 = (b[0] - a[0]) * (p1[1] - a[1]) - (b[1] - a[1]) * (p1[0] - a[0])
    cp2 = (b[0] - a[0]) * (p2[1] - a[1]) - (b[1] - a[1]) * (p2[0] - a[0])
    return cp1 * cp2 >= 0

def point_in_triangle(p, a, b, c):
    return (on_same_side(p, a, b, c) and
            on_same_side(p, b, a, c) and
            on_same_side(p, c, a, b))

def calculate_intersections(triangles, x_set, y_set):
    max_sum = 0
    best_point = (float('inf'), float('inf'))
    
    for x in x_set:
        for y in y_set:
            NRO = sum(1 for t in triangles if any((x == vx for vx, vy in t)))
            NRV = sum(1 for t in triangles if any((y == vy for vx, vy in t)))
            current_sum = NRO + NRV
            if current_sum > max_sum or (current_sum == max_sum and (x < best_point[0] or (x == best_point[0] and y < best_point[1]))):
                max_sum = current_sum
                best_point = (x, y)
    
    return best_point

def main():
    input_file = "dispozitiv.in"
    output_file = "dispozitiv.out"
    
    triangles = read_input(input_file)
    
    x_set = set()
    y_set = set()
    
    for t in triangles:
        for x, y in t:
            x_set.add(x)
            y_set.add(y)
    
    xD, yD = calculate_intersections(triangles, x_set, y_set)
    
    write_output(output_file, xD, yD)

if __name__ == "__main__":
    main()

</syntaxhighlight>