Cod sursa(job #2375461)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 8 martie 2019 09:40:39
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include<bits/stdc++.h>
using namespace std;

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

typedef pair<double,double> pct;

pct V[100001];
int k,st[100001];
pct start;

int n;

double crd(pct x, pct y, pct z)
{
    return (x.first*y.second + z.first*x.second + y.first*z.second) - (z.first*y.second + z.second * x.first + y.first * x.second);
}

bool cmp(pct x,pct y)
{
    return crd(V[1],x,y)>0;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
    {
        f>>V[i].first>>V[i].second;
        if(V[1]>V[i])
            swap(V[i],V[1]);
    }
    sort(V+2,V+n+1,cmp);
    st[++k]=1;
    for(int i=2;i<=n;++i)
    {
        while(k>1 && crd(V[st[k-1]],V[st[k]],V[i])<=0)
            k--;
        st[++k]=i;
    }
    g<<k<<'\n';
    for(int i=1;i<=k;++i)
        g<<fixed<<setprecision(6)<<V[st[i]].first<<' '<<V[st[i]].second<<'\n';
}