Cod sursa(job #1852305)

Utilizator tudi98Cozma Tudor tudi98 Data 20 ianuarie 2017 17:57:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

const int Nmax = 1000;

int n;

struct Point
{
    double x,y,id;
    Point(): x(0),y(0),id(0) {}
};

Point p[Nmax+1];
int ST[Nmax+1];

inline double crossProduct(const Point &A,const Point &B,const Point &C) {
    return 1LL * A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y);
}

inline bool comp(const Point &A,const Point &B) {
    return crossProduct(p[1],A,B) < 0;
}

void solve()
{
    for (int i = 2; i <= n; i++)
        if ((p[i].x == p[1].x && p[i].y < p[1].y) || p[i].x < p[1].x)
            swap(p[i],p[1]);

    sort(p+2,p+n+1,comp);

    ST[0] = 2; ST[1] = 1; ST[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        while (ST[0] >= 2 && crossProduct(p[ST[ST[0]-1]],p[ST[ST[0]]],p[i]) > 0)
            ST[0]--;
        ST[++ST[0]] = i;
    }
}

int main()
{
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");

    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> p[i].x >> p[i].y;
        p[i].id = i;
    }

    solve();

    fout << ST[0] << "\n";
    for (int i = 1; i <= ST[0]; i++)
        fout << fixed << setprecision(7) << p[ST[i]].x << " " << p[ST[i]].y << "\n";
}