Cod sursa(job #1395543)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 21 martie 2015 12:18:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
//#include <iostream>
#include <fstream>
using namespace std;

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

#include <algorithm>
#define x first
#define y second
#define mp make_pair
#define db double
#define LE 120666
#include <iomanip>
#define cout g

pair<db,db> B[LE];
pair<db,db> Pmin;

db cross(pair<db,db> i1,pair<db,db> i2,pair<db,db> i3)
{
    i2.x-=i1.x,i3.x-=i1.x;
    i2.y-=i1.y,i3.y-=i1.y;
    return (i2.y*i3.x-i2.x*i3.y);
}

bool comp (pair<db,db> i1,pair<db,db> i2)
{
    db val=cross(Pmin,i1,i2);
    if (val==0) return i1.y>i2.y;
    return (val>0.0);
}

int solve(pair<db,db> A[],int N)
{
    Pmin=A[1];
    int i,ind_min=1;

    for(i=1; i<=N; ++i)
        if (A[i].y<Pmin.y)
            Pmin=A[i],ind_min=i;

    swap(A[ind_min],A[1]);
    sort(A+2,A+1+N,comp);

    int k=2;
    B[1]=A[1];
    B[2]=A[2];

    for(i=3; i<=N; ++i)
    {
        while (k>=2&&cross(B[k-1],B[k],A[i])<0.0) --k;
        B[++k]=A[i];
    }

    return k;
}

pair<db,db> V[LE];

int main()
{
    int n,i;

    f>>n;
    for(i=1; i<=n; ++i) f>>V[i].x>>V[i].y;

    int k=solve(V,n);

    cout<<k<<'\n';

    cout<<fixed;
    cout<<setprecision(10);

    for(i=k; i>=1; --i)
    {
        cout<<B[i].x<<" "<<B[i].y<<'\n';
    }

    return 0;
}