Cod sursa(job #1405337)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 29 martie 2015 01:53:35
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>

using namespace std;

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

//Infasuratoare convexa fara puncte coliniare

pair <int,int> x,y;

struct point
{
    double x,y;
}v[120001];

int n,i,k,p,s[120001],t,j;
double eps=1e-12;

inline double det (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)
{
    double d = det (v[1],A,B);
    if (d == 0)
    {
        if (A.x == B.x)
        {
            return A.y < B.y;
        }

        return A.x < B.x;
    }

    return d > 0;
}

int main ()
{
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    int mini=1;
    for (int i=2; i<=n; ++i)
    {
        if (fabs(v[i].x - v[mini].x) > eps) {if (v[i].x < v[mini].x) mini=i;}
        else if (v[i].y < v[mini].y) mini=i;
    }

    point temp = v[1];
    v[1]=v[mini];
    v[mini]=temp;

    sort (v+2,v+n+1,cmp);

    s[1]=1;
    s[2]=2;
    k=2;

    for (i=3; i<=n; ++i)
    {
        while (k>=2 && det(v[s[k-1]],v[s[k]],v[i]) <= 0) k--;
        s[++k]=i;
    }


    fout<<k<<"\n";
    fout<<fixed<<setprecision(6);
    for (i = 1; i <= k; ++i)
    {
        fout << v[s[i]].x << " " << v[s[i]].y << "\n";
    }
}