Cod sursa(job #2007191)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 2 august 2017 10:41:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n,mipoz,st[120005],vf;
typedef pair <double,double> punct;
punct p[120010];
double determinant(punct A,punct B,punct C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int comp(punct A,punct B)
{
    if(determinant(p[1],A,B)<0) return true;
    return false;
}
void read()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>p[i].x>>p[i].y;
        if(p[i]<p[mipoz]) mipoz=i;
    }
}
int main()
{
    read();
    swap(p[1],p[mipoz]);
    sort(p+2,p+n+1,comp);
    st[++vf]=1;
    for(int i=2;i<=n;++i)
    {
        while(vf>1&&determinant(p[st[vf-1]],p[st[vf]],p[i])>0) --vf;
        st[++vf]=i;
    }
    g<<vf<<'\n';
    while(vf)
    {
        g<<setprecision(6)<<fixed<<p[st[vf]].x<<' '<<p[st[vf]].y<<'\n';
        --vf;
    }
    return 0;
}