Pagini recente » Cod sursa (job #3032004) | Cod sursa (job #1669161) | Cod sursa (job #1872184) | PreOJI 2016 - Clasament - Clasele 11-12 | Cod sursa (job #2866922)
#include <fstream>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f ("rubarba.in");
ofstream g ("rubarba.out");
int n;
double aria;
int sol[100005], k;
struct point {
int x, y;
}v[100005];
int Orientare (point a, point b, point c)
{
int aux = (b.y - a.y) * (c.x - b.x) - (c.y - b.y) * (b.x - a.x);
if (aux == 0) return 0;
if (aux < 0) return 1; // c la stanga lui [a,b]
if (aux > 0) return 2;
}
int distanta (point a, point b)
{
return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
void Infasuratoare ()
{
int l = 0;
for (int i=1; i<n; i++)
if (v[i].x < v[l].x)
l = i;
int a = l, b;
do
{
k ++; sol[k] = a;
b = (a + 1) % n;
for (int i=0; i<n; i++)
{
if (Orientare(v[a], v[b], v[i]) == 2)
b = i;
else if (Orientare(v[a], v[b], v[i]) == 0)
{
if (distanta(v[a], v[b]) < distanta(v[a], v[i]))
b = i;
}
}
a = b;
}while(a != l);
}
int main()
{
f >> n;
for (int i=0; i<n; i++)
f >> v[i].x >> v[i].y;
Infasuratoare();
k ++;
sol[k] = sol[1];
for (int i=1; i<=k; i++)
{
aria += (v[sol[i]].x * v[sol[i+1]].y);
aria -= (v[sol[i]].y * v[sol[i+1]].x);
}
if (aria < 0) aria = -aria;
aria /= 2.0;
g << fixed << setprecision(2);
g << aria;
return 0;
}