Cod sursa(job #1971264)

Utilizator GinguIonutGinguIonut GinguIonut Data 20 aprilie 2017 06:56:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

#define nMax 120001
#define pb push_back
#define mkp make_pair
#define x first
#define y second

using namespace std;

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

int n;
pair<double, double> pct[nMax], stck[nMax];

double det(const pair<double, double> &a, const pair<double, double> &b, const pair<double, double> &c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-a.y*b.x-a.x*c.y;
}

bool cmp(const pair<double, double> &a, const pair<double, double> &b)
{
    return det(pct[1], a, b)>0;
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>pct[i].x>>pct[i].y;
    int poz=1;
    for(int i=2; i<=n; i++)
        if(pct[i]<pct[poz])
            poz=i;
    swap(pct[1], pct[poz]);
    sort(pct+2, pct+n+1, cmp);

    int top=0;
    stck[++top]=pct[1];
    stck[++top]=pct[2];
    for(int i=3; i<=n; i++)
    {
        while(top>=2 && det(stck[top-1], stck[top], pct[i])<0)
            top--;
        stck[++top]=pct[i];
    }

    fout<<top<<'\n';
    for(int i=1; i<=top; i++)
        fout<<fixed<<setprecision(6)<<stck[i].x<<" "<<stck[i].y<<'\n';
}