Cod sursa(job #2367027)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 5 martie 2019 00:26:31
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<bits/stdc++.h>
#define point pair<double,double>

using namespace std;

const int maxN=120005;

point v[maxN];
inline double det(point a,point b,point c)
{
    double d=(a.first*b.second)+(b.first*c.second)+(a.second*c.first)
        -(c.first*b.second)-(b.first*a.second)-(a.first*c.second);

    return d;
}

bool cmp(point a,point b)
{
    return det(v[1],a,b)>0;
}
int n,st[maxN],vf;

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

    fin>>n;

    for(int i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;

    for(int i=2;i<=n;i++)
        if(v[i].first<v[1].first  || (v[i].first==v[1].first && v[i].second<v[1].second)) swap(v[i],v[1]);

    sort(v+2,v+n+1,cmp);
    st[++vf]=1;
    st[++vf]=2;
    for(int i=3;i<=n;i++)
    {
        while(vf>=2 && det(v[st[vf-1]],v[st[vf]],v[i])<0) vf--;
        st[++vf]=i;
    }

    fout<<vf<<'\n';

    for(int i=1;i<=vf;i++)
        fout<<setprecision(12)<<fixed<<v[st[i]].first<<' '<<v[st[i]].second<<'\n';


    return 0;
}