Cod sursa(job #1880929)

Utilizator ClaudiuHHiticas Claudiu ClaudiuH Data 15 februarie 2017 23:56:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda becreative16 Marime 1.15 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define INF 0x3f3f3f3f;
#define NMAX 120005
using namespace std;
 
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
 
struct punct
{
    double x,y;
}pct[NMAX],mini,st[NMAX];

int N;

double Aria(punct a, punct b, punct c)
{
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
 
int comp(const punct& a, const punct& b)
{
    return (Aria(a,mini,b) > 0);
}
 
int main()
{
    int i, poz;
    fin >> N;
 
    mini.x = mini.y = INF;
    for(i=1; i<=N; i++)
    {
        fin>>pct[i].x>>pct[i].y;
        if(pct[i].x < mini.x)
        {
            mini = pct[i];
            poz = i;
        }
        else if(pct[i].x == mini.x && pct[i].y < mini.y)
            mini = pct[i], poz = i;
    }
    swap(pct[1],pct[poz]);
 
    sort(pct+2,pct+N+1,comp);
 
    st[1] = mini;
    int po = 2;
 
    for(i = po; i<=N;i++)
    {
        while(po > 2 && Aria(st[po-2], st[po-1], pct[i])>=0)
            po--;
        st[po] = pct[i];
        po++;
    }
 
    fout<<po-1<<'\n';
    fout<<setprecision(6)<<fixed;
    for(i=1; i<po; ++i)
        fout<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}