Expand

expand

== include(page="template/taskheader" task_id="expand") ==

$-K0kalaru47 are un poligon.-$
Se dă un poligon convex cu $N$ vârfuri. Puteţi muta un vârf $A$ al poligonului într-un alt punct $B$ din plan, doar dacă distanţa euclidiană de la $A$ la $B$ este maxim $R$.
 
h2. Cerinţă
 
Mutaţi vârfurile poligonului astfel încât aria poligonului pe care îl obţineţi să fie cât mai mare.
 
h2. Punctare
 
**Aveţi acces la teste** "**aici**":https://infoarena.ro/teste-expand?action=attach-list **şi la poligoanele comisiei** "**aici**":https://www.youtube.com/watch?v=dQw4w9WgXcQ
 
Fie $A{~max~}$ aria poligonului obţinut de comisie, $A{~concurent~}$ aria poligonului obţinut de concurent pe acelaşi test şi $A{~init~}$ aria poligonului din input pe acel test.
Fie <tex>P = \frac {(Aconcurent - Ainit)}{(Amax - Ainit)} * 100</tex>.
 
Numărul de puncte pe care îl primiţi pe un test este egal cu:
 
table(scoruri). |_. P |_. punctaj |
| $P < 30$
| $0 puncte$
|
| $30 &le; P < 50$
| $1 punct$
|
| $50 &le; P < 60$
| $2 puncte$
|
| $60 &le; P < 70$
| $3 puncte$
|
| $70 &le; P < 80$
| $4 puncte$
|
| $80 &le; P < 90$
| $5 puncte$
|
| $90 &le; P < 95$
| $6 puncte$
|
| $95 &le; P < 98$
| $7 puncte$
|
| $98 &le; P < 99$
| $8 puncte$
|
| $99 &le; P < 100$
| $9 puncte$
|
| $100 &le; P$
| $10 puncte$
|

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $expand.in$ pe prima linie se va afla un număr $T$, reprezentând numărul testului. Pe a doua linie se vor afla două numere naturale $N$ şi $R$. Pe următoarele $N$ linii se vor câte două numere reale, separate printr-un spaţiu, reprezentând coordonatele $x$ şi $y$ ale vârfurilor primului poligon. Vârfurile poligonului sunt date în ordine trigonometrică sau invers trigonometrică.

Fişierul de intrare $expand.in$ ...

h2. Date de ieşire

În fişierul de ieşire $expand.out$ veţi afişa pe $N$ linii coordonatele ce alcătuiesc poligonul, anume, pe linia $i$ se vor afla coordonatele la care aţi mutat punctul $i$.

În fişierul de ieşire $expand.out$ ...

h2. Restricţii

* $2 ≤ N ≤ 50$
* Se garantează ca dacă putem muta un vârf A al poligonului într-un punct B din plan, atunci nu există un alt vârf al poligonului care poate fi mutat în B.
* Pe testele $1$ şi $2$, poligoanele din input sunt regulate.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. expand.in |_. expand.out |

| 0
4 1
0 0
4 0
4 4
0 4
| -0.707107 -0.707107
4.70711 -0.707107
4.70711 4.70711
-0.707107 4.70711

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Mutăm vârful $A$ în $A'$, vârful $B$ în $B'$, vârful $C$ în $C'$ şi vârful $D$ în $D'$.
 
!problema/expand?exemplu.png!

...

== include(page="template/taskfooter" task_id="expand") ==