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

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

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>