| Fişierul intrare/ieşire: | vantu.in, vantu.out | Sursă | AGM 2019, runda finala |
| Autor | Alexa Tudose, Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 3.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Vantu
The wind, it beats me in the face,
And I have no feeling for life,
Oh, soul ... what a larcenous world.
My friends, with whom I have drunk,
Where are they ? Oh, soul ... friends like two coins
I’m finished, and I’m changing my page with all,
And the vagabond’s mothers,
They are evil and twisted,
My friends, they are.
(Nicolae Guta)
Se da un poligon convex cu N varfuri. Pentru un K dat, selectati o submultime S aleatoare ce contine K varfuri a poligonului. Considerati poligonul convex ce se formeaza daca luam coordonatele lui S in ordine trigonometrica. Care e valoarea anticipata a ariei poligonlui format ?
Date de intrare
Fişierul de intrare vantu.in va incepe cu numerele N si K. Urmatoarele N randuri vor contine coordonatele punctelor poligonului dat.
Date de ieşire
În fişierul de ieşire vantu.out, daca media ceruta este raportul dintre p si q, afisati p * q-1 mod 998244353, unde q-1 este inversul modular al lui q modulo 998244353.
Restricţii
- 3 ≤ N ≤ 70.000
- 3 ≤ K ≤ N
- -109 ≤ coordonatele punctelor ≤ 109
Exemplu
| vantu.in | vantu.out |
|---|---|
| 4 4 0 0 1 0 1 1 0 1 | 1 |
| 4 3 0 0 1 0 1 1 0 1 | 499122177 |
