Fişierul intrare/ieşire:aria.in, aria.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aria

Dându-se un poligon convex cu N vârfuri, să se determine aria acestuia.

Date de intrare

Fişierul de intrare aria.in conţine pe prima linie numărul de puncte N, date în ordine trigonometrică, iar pe urmatoarele N linii 2 numere reale, xi şi yi, care reprezintă coordonatele punctului i.

Date de ieşire

Fişierul de ieşire aria.out va conţine un singur număr reprezentând aria poligonului dat.

Restricţii

  • 1 ≤ N ≤ 100 000
  • -1 000 000 ≤ xi, yi ≤ 1 000 000
  • Rezultatul se va afişa cu o precizie de 10-5.

Exemplu

aria.inaria.outExplicaţie
4
-2 -2
2 -2
2 2
-2 2
16
Aria poligonului dat este de fapt aria dreptunghiului din figură.

Indicaţii de rezolvare

Desi problema are ca date de intrare poligoane convexe, rezolvarea de mai jos este valabila pentru orice tip de poligoane. Pentru a calcula aria unui poligon A1A2A3..An, vom considera un punct P arbitrar ales în plan. Vom "împărţi" poligonul în triunghiuri de forma PAiAi+1 (considerăm că A1 = An+1) şi vom calcula "aria cu semn" Ti a fiecărui triunghi (în formula ariei nu vom folosi funcţia de valoare absolută). Distingem în acest moment două cazuri:

  • Poligonul are vârfurile orientate trigonometric. Pentru fiecare latură "spre dreapta", aria Ti corespunzătoare va fi negativă, iar pentru fiecare latură "spre stânga", aria Ti corespunzătoare va fi pozitivă.
  • Poligonul are vârfurile orientate antitrigonometric. Pentru fiecare latură "spre dreapta", aria Ti corespunzătoare va fi pozitivă, iar pentru fiecare latură "spre stânga", aria Ti corespunzătoare va fi negativă.

În ambele cazuri, efectuând suma algebrică a ariilor Ti vom obţine aria poligonului (deoarece ariile negative vor "anula" zonele corespunzătoare ariilor pozitive care se află în afara poligonului).

Dacă alegem punctul P(0, 0), fiecare arie Ti devine:
\begin{math}T_{i} = \frac{1}{2}\cdot \left\left|\begin{array}{ccc}
\ 0 & 0 & 1\
x_i & y_i & 1\
x_{i+1} & y_{i+1} & 1\end{array}\right|\right = \frac{1}{2}\cdot \left(x_i\cdot y_{i+1}-x_{i+1}\cdot y_i\right)
\end{math}

Formula finală devine:
\begin{math}
A = \displaystyle\sum_{i=1}^n T_i = \frac{1}{2}\cdot\displaystyle\sum_{i=1}^n \left(x_i\cdot y_{i+1}-x_{i+1}\cdot y_i\right)}
\end{math}

Această formulă reprezintă "aria cu semn" a poligonului (o arie pozitivă indică parcurgerea vârfurilor în ordine trigonometrică, iar o arie negativă, parcurgerea in ordine antitrigonometrică). O sursă care se bazează pe această soluţie obţine 100 puncte.

Aplicaţii

O primă aplicaţie ar fi coliniaritatea a N puncte. Pentru ca N puncte să fie coliniare, trebuie ca aria determinată de poligonul asociat acestora să fie 0. O altă aplicaţie drăguţă este următoarea : dacă un punct se află în interiorul unui poligon convex. Soluţia presupune calcularea ariei cu semnn a triunghiurilor determinate de oricare 2 puncte de pe acest poligon şi punctul căutat. Dacă toate ariile au acelasi semn (+ sau -), atunci punctul se află în interiorul poligonului.

Printre problemele care folosesc aria unui poligon se numără :

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content