Cod sursa(job #3216594)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 18 martie 2024 13:12:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,poz,k,i;
#define PAIR pair <double,double>
PAIR V[120002],st[120002],aux;
/*int cadran(const PAIR &a)
{
    double x=a.first;
    double y=a.second;
    if(x>0&&y>=0)
        return 1;
    if(x>=0&&y<0)
        return 4;
    if(x<=0&&y>0)
        return 2;
    return 3;
}*/
double det(const PAIR &a,const PAIR &b,const PAIR &c)
{
    return (b.first-a.first)*(c.second-a.second)-(c.first-a.first)*(b.second-a.second);
}
bool cmp(const PAIR &a,const PAIR &b)
{
    return det(V[1],a,b)>0;
}
int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>V[i].first>>V[i].second;
    poz=1;
    for(i=2;i<=n;i++)
        if(V[i]<V[poz])
            poz=i;
    swap(V[1],V[poz]);
    sort(V+2,V+n+1,cmp);
    st[1]=V[1];
    st[2]=V[2];
    k=2;
    for(i=3;i<=n;i++)
    {
        while(k>=2&&det(st[k-1],st[k],V[i])<0)
            k--;
        st[++k]=V[i];
    }
    fout<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<setprecision(9)<<fixed<<st[i].first<<" "<<st[i].second<<"\n";
    return 0;
}