Cod sursa(job #1957910)

Utilizator valentinoMoldovan Rares valentino Data 7 aprilie 2017 20:52:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#define NM 120005
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct point
{
    double x, y;
};

point stiva[NM], v[NM], p[NM];
int n, vf;

inline double cross(const point& a, const point& b, const point& c)
{
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline bool cmp(const point& a, const point& b)
{
    return cross(v[1], a, b) < 0;
}

inline bool cmp2(const point& a, const point& b)
{
    return cross(p[1], a, b) > 0;
}

void Read()
{
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        f >> v[i].x >> v[i].y;
    }
}

void ConvexHull()
{
    int poz = 1;
    for(int i = 2; i <= n; ++i)
    {
        if((v[i].x < v[poz].x) || (v[i].x == v[poz].x && v[i].y < v[poz].y))
            poz = i;
    }
    swap(v[1], v[poz]);
    sort(v + 2, v + n + 1, cmp);//Sortare antitrigonometrica
    stiva[1] = v[1];
    stiva[2] = v[2];
    vf = 2;
    for(int i = 3; i <= n; ++i)
    {
        while(vf >= 2 && cross(stiva[vf - 1], stiva[vf], v[i]) > 0)
            vf--;
        stiva[++vf] = v[i];
    }
    g << vf << '\n';
    for(int i = vf; i >= 1; --i)
    {
        g << fixed;
        g << setprecision(9) << stiva[i].x << ' ' << stiva[i].y << '\n';
        p[vf - i + 1] = stiva[i];
    }
}

void Aria()
{
    double s = 0;
    int poz = 1;
    for(int i = 1; i <= vf; ++i)
    {
        if((p[i].x < p[poz].x) || (p[i].x == p[poz].x && p[i].y < p[poz].y))
            poz = i;
    }
    swap(p[1], p[poz]);
    sort(p + 2, p + vf + 1, cmp2);//Sortare trigonometrica

    p[vf + 1] = p[1];
    for(int i = 1; i <= vf; ++i)
    {
        s += (p[i].x * p[i + 1].y - p[i].y * p[i + 1].x);
    }
    s /= 2.0;
    if(s < 0) s = -s;
    g << "Aria poligonului convex: " << setprecision(5) << s;

}

int main()
{
    Read();
    ConvexHull();
    //Aria();
}