Fişierul intrare/ieşire:superpoligon.in, superpoligon.outSursăJunior Challenge 2018
AutorAlexandru PetrescuAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test0.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Superpoligon

Anul trecut, Marcel era expert in figuri geometrice simple. Stia sa gaseasca pana si numarul de perechi de triunghiuri confundabile care se pot forma, alegand ca varfuri puncte dintr-un set dat. Mai nou, Marcel s-a şmeckerit si va propune sa rezolvati o generalizare:

Cerinta

Se dau N puncte distincte, un numar K si un numar M. Pentru fiecare r de la 3 la K, se cere numarul modulo M de perechi ordonate de poligoane confundabile de cate r puncte care se pot forma, alegand ca varfuri puncte dintr-un set dat. Fiecare poligon se poate auto-intersecta, dar nu poate poate contine acelasi punct de 2 ori.

Doua poligoane se considera confundabile daca exista o translatie astfel incat poligoanele sa se suprapuna perfect. De exemplu, orice poligon e confundabil cu el insusi. Atentie: Suprapunerea se face verifcand daca varfurile coincid, nu daca liniile coincid - fapt relevant in cazul punctelor coliniare: (0, 0) - (0, 1) - (0, 3) e diferit de (0, 0) - (0, 2) - (0, 3).

Doua poligoane sunt identice daca punctele unuia se obtin printr-o permutare circulara a altuia. De exemplu, (0, 0) - (0, 1) - (0, 2) e acelasi poligon cu (0, 1) - (0, 2) - (0, 0), dar e diferit de (0, 0) - (0, 2) - (0, 1).

Date de intrare

Fişierul de intrare superpoligon.in contine pe prima linie numerele naturale N, K si M (108 ≤ M ≤ 109 + 7) si pe urmatoarele N linii cate 2 numere intregi cu valoarea absoluta mai mica decat 109 reprezentand coordonatele punctelor.

Date de ieşire

În fişierul de ieşire superpoligon.out se vor afla K - 2 linii, pe a i-a dintre ele fiind scris restul numarului cerut pentru r = i + 2 modulo M.

Subtaskuri

  • Subtask 1 - 10 puncte (testele 1 şi 2): 3 ≤ K ≤ N ≤ 8, M = 109 + 7
  • Subtask 2 - 30 de puncte (testele 3-8): 3 = K ≤ N ≤ 100, M = 109 + 7
  • Subtask 3 - 15 de puncte (testele 9-11): 3 ≤ K ≤ N ≤ 40, M = 109 + 7
  • Subtask 4 - 15 de puncte (testele 12-14): 3 ≤ K ≤ N ≤ 40
  • Subtask 5 - 15 de puncte (testele 15-17): 3 ≤ K ≤ N ≤ 1.000, M = 109 + 7
  • Subtask 6 - 15 de puncte (testele 18-20): 3 ≤ K ≤ N ≤ 1.000

Exemplu

superpoligon.insuperpoligon.out
8 8 1000000007
0 0
0 2
1 1
1 3
3 0
3 2
4 1
4 3
160
456
1344
3360
5760
5040

Explicaţie

Exista 160 de perechi de triunghiuri confundabile, cum ar fi { (0, 0), (0, 2), (1, 1) } cu { (3, 0), (3, 2), (4, 1) }.
Observati ca { (0, 0), (0, 2), (1, 1) } si { (3, 0), (3, 2), (4, 1) } este considerata o perechie diferita de { (0, 0), (1, 1), (0, 2) } cu { (3, 0), (4, 1), (3, 2) }.
Remarcati ca { (0, 0), (0, 2), (1, 1) } si { (3, 0), (3, 2), (4, 1) } este considerata o pereche identica cu { (0, 2), (1, 1), (0, 0) } si { (3, 2), (4, 1), (3, 0) }.
De asemenea, { (0, 0), (0, 2), (1, 1) } si { (3, 0), (3, 2), (4, 1) } este considerata o pereche diferita de { (3, 0), (3, 2), (4, 1) } si { (0, 0), (0, 2), (1, 1) }

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?