0153 - Drept

Enunt

La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii: 1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale 2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy 3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Cerinţa

Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Date de intrare

Pe prima linie a fişierului de intrare drept.in se află numărul natural N reprezentând numărul de segmente orizontale. Pe următoarele N linii se află câte 3 numere naturale y x1 x2 reprezentând coordonatele segmentelor astfel: y – coordonata verticală (ordonata), x1 şi x2 – coordonatele orizontale (abscisele).

Date de ieșire

Fişierul de ieşire drept.out va conţine un singur număr, reprezentând restul împărţirii numărului total de dreptunghiuri speciale la 946021.

Restricţii şi precizări

• 1 ≤ N ≤ 50.000
• 0 ≤ x1≤ x2 ≤ 1.000.000.000
• 0 ≤ y ≤ 1000
• Vârfurile oricărui dreptunghi special sunt distincte două câte două şi nu pot avea toate aceeaşi ordonată
• Pentru un număr de teste în valoare de 60 de puncte, N ≤ 5000

Exemplul 1

drept.in

3 2 2 3 1 1 4 3 3 4

drept.out

2

Exemplul 2

drept.in

4 3 1 5 2 2 4 1 2 3 1 2 5

drept.out

12

Rezolvare

<syntaxhighlight lang="python" line> def read_input(filename):

   with open(filename, 'r') as file:
       n = int(file.readline().strip())
       segments = []
       for _ in range(n):
           y, x1, x2 = map(int, file.readline().strip().split())
           segments.append((y, x1, x2))
   return segments

def write_output(filename, result):

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

def count_special_rectangles(segments):

   from collections import defaultdict
   import itertools

   MOD = 946021

   level_segments = defaultdict(list)
   for y, x1, x2 in segments:
       level_segments[y].append((x1, x2))

   ys = sorted(level_segments.keys())
   count = 0

   for y1, y2 in itertools.combinations(ys, 2):
       x_points = set()
       for x1, x2 in level_segments[y1]:
           for x in range(x1, x2 + 1):
               x_points.add(x)
       for x1, x2 in level_segments[y2]:
           for x in range(x1, x2 + 1):
               if x in x_points:
                   x_points.add(x)
       
       x_points = sorted(x_points)
       k = len(x_points)
       if k >= 2:
           
           count = (count + k * (k - 1) // 2) % MOD

   return count

def main():

   input_file = "drept.in"
   output_file = "drept.out"
   segments = read_input(input_file)
   result = count_special_rectangles(segments)
   write_output(output_file, result)

if __name__ == "__main__":

   main()

</syntaxhighlight>