Cod sursa(job #1651385)

Utilizator VoicencuVoicencu Teodor Octavian Voicencu Data 13 martie 2016 10:41:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define point pair<double,double>

using namespace std;

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

pair <double,double> p[120001];
int n,mn,st[120001],top;

double det(point x,point y,point z)
{
    return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}

bool cmp(point x,point y)
{
        return det(p[1],x,y)>0;
}

int main()
{
    f>>n;
    mn=1;
    for(int i=1;i<=n;i++)
    {
        f>>p[i].first>>p[i].second;
        if(p[i].second<p[mn].second) mn=i;
        else if(p[i].second==p[mn].second and p[i].first<p[mn].first) mn=i;
    }
    swap(p[1],p[mn]);
    sort(p+2,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        while(top>=2 and det(p[i],p[st[top]],p[st[top-1]])>0) top--;
        st[++top]=i;
    }
    g<<top<<'\n';
    for(int i=1;i<=top;i++)
    {
        g<<fixed<<setprecision(6)<<p[st[i]].first<<" "<<p[st[i]].second<<'\n';
    }
    return 0;
}