Fişierul intrare/ieşire:vantu.in, vantu.outSursăAGM 2019, runda finala
AutorAlexa Tudose, Tamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test7 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.invantu.out
4 4
0 0
1 0
1 1
0 1
1
4 3
0 0
1 0
1 1
0 1
499122177
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?