Cod sursa(job #2132307)

Utilizator MoleRatFuia Mihai MoleRat Data 15 februarie 2018 17:53:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef struct Cr
{
    double x;
    double y;
} CR;
CR A[120010];
int Stv[120010];
int n;
bool F[120010];
bool cmp(CR a,CR b)
{
    if (a.x<b.x)
        return 1;
    else if (a.x>b.x)
        return 0;
    return a.y<b.y;
}
double rt(CR Or,CR a,CR b)
{
    return (a.x - Or.x) * (b.y - Or.y) - (b.x - Or.x) * (a.y - Or.y);
}
int main()
{
    fin>>n;
    for (int i=1; i<=n; i++)
        fin>>A[i].x>>A[i].y;
    sort(A+1,A+n+1,cmp);
    Stv[1]=1;
    Stv[2]=2;
    int cap=2;
    F[2]=1;
    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p)))
    {
        if (F[i]==0)
        {
            while (cap>=2 && rt(A[Stv[cap-1]],A[Stv[cap]],A[i])<(double)(1e-10))
                F[Stv[cap--]]=0;
            Stv[++cap]=i;
            F[i]=1;
        }
    }
    fout << cap - 1 << "\n";
    fout << setprecision(6) << fixed;
    for (int i = 1; i < cap; ++i)
        fout << A[Stv[i]].x << " " << A[Stv[i]].y << "\n";
    return 0;
}