Cod sursa(job #1580471)

Utilizator metrix007Lungu Ioan Adrian metrix007 Data 25 ianuarie 2016 21:23:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <vector>
#include <utility>
#define INF  999999
#define NMAX 120002
#define x first
#define y second

using namespace std;
typedef pair<double,double> punct;

punct stiva[NMAX],v[NMAX];
int n,pos;

double sens(punct d1,punct d2,punct d3)
{
    return ((d2.x-d1.x)*(d3.y-d1.y) - (d3.x-d1.x)*(d2.y-d1.y));
}

bool comp(punct a,punct b)
{
    return sens(v[1],a,b)<0;
}

void Sort()
{
    pos =1;
    for(int i=1;i<=n;i++)
    {
        if(v[i]<v[pos])
        {
            pos = i;
        }
    }
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,comp);
}

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

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

    Sort();
    int vf = 2;
    stiva[1] = v[1];
    stiva[2] = v[2];
    for(int i=3;i<=n;i++)
    {
        while(vf>=2 && sens(stiva[vf-1],stiva[vf],v[i])>0)
            vf--;
        stiva[++vf] = v[i];
    }
    out << vf <<'\n';
    for(int i=vf;i>=1;i--)
    {
        out << fixed << setprecision(12) << stiva[i].x << " " << stiva[i].y << "\n";
    }
    return 0;
}