Fişierul intrare/ieşire:ultrapoligon.in, ultrapoligon.outSursăSummer Challenge 2019
AutorAlexandru LuchianovAdăugată deAlexandruLuchianov1Alex Luchianov AlexandruLuchianov1
Timp execuţie pe test0.6 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ultrapoligon

Se dau N puncte care reprezinta un poligon convex.

Se defineste un subpoligon ca fiind poligonul determinat de un subset de puncte ale celui initial. Un poligon este propriul sau subpoligon.
Se cere dublul sumei ariilor tuturor subpoligoanelor poligonului din input.

Date de intrare

Fişierul de intrare ultrapoligon.in va contine pe prima linie numarul N iar pe urmatoarele N linii se vor afla cate 2 numere care reprezinta coordonatele punctelor.

Date de ieşire

În fişierul de ieşire ultrapoligon.out se va afisa dublul sumei ariilor subpoligoanelor.

Restricţii

  • ATENTIE!!! Deoarece se poate demonstra ca raspunsul este intreg, iar numerele mari nu mai sunt la moda, va este cerut sa afisati raspunsul modulo 1.000.000.007
  • Toate coordonatele sunt numere intregi cuprinse intre 0 si 109
  • Pentru 20 de puncte, N ≤ 18
  • Pentru alte 40 de puncte, N ≤ 2.000
  • Pentru restul de 40 de puncte, N ≤ 100.000
  • Punctele sunt date in input in ordine trigonometrica
  • Nu exista 3 puncte consecutive coliniare

Exemplu

ultrapoligon.inultrapoligon.out
4
0 0
1 0
1 1
0 1
6
14
431 0
983 14
997 331
994 511
975 679
910 893
849 937
830 947
557 985
235 977
16 892
6 778
2 569
30 12
295591745

Explicaţie

In primul exemplu poligonul nostru este un patrat. Subpoligoanale sale sunt:
Patratul { (0,0), (1,0), (1,1), (0,1) } cu aria 1 si triunghiurile cu aria 0.5:
{ (1,0), (1,1), (0,1) }
{ (0,0), (1,1), (0,1) }
{ (0,0), (1,0), (0,1) }
{ (0,0), (1,0), (1,1) }
Dublul sumei ariilor este 2 * (1 + 0.5 * 4) = 2 * 3 = 6

Pentru al doilea exemplu va trebui sa ne credeti pe cuvant.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?