| Fişierul intrare/ieşire: | ultrapoligon.in, ultrapoligon.out | Sursă | Summer Challenge 2019 |
| Autor | Alexandru Luchianov | Adăugată de |  Alex Luchianov •AlexandruLuchianov1 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ultrapoligon.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.
