Cod sursa(job #2166608)

Utilizator usureluflorianUsurelu Florian-Robert usureluflorian Data 13 martie 2018 17:57:45
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 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> usu;
usu p[120010];
inline long double det(const usu &t1,const usu &t2,const usu &t3)
{
      return t1.x*t2.y+t2.x*t3.y+t3.x*t1.y-t3.x*t2.y-t1.x*t3.y-t2.x*t1.y;
}
inline bool cmp(const usu &t1,const usu &t2)
{
      return det({p[1].x,p[1].y},t1,t2)<0;
}
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,cmp);
    st[++vf]=1;
    for(int i=2;i<=n;++i)
    {
        while(vf>1&&det(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;
}