Cod sursa(job #2287815)

Utilizator vladsirbu23Vlad Sirbu vladsirbu23 Data 22 noiembrie 2018 15:43:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
#define punct pair<double,double>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
vector <punct> v;
int N;
int st[120010],st2[120010];
double det(punct a,punct b,punct c)
{
    double rez;
    rez=a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
    return rez;
}
int main()
{
    int i,niv,niv2;
    double a,b;
    v.push_back(make_pair(0,0));
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>a>>b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin()+1,v.begin()+N+1);
    st[1]=1;
    st[2]=2;
    niv=2;
    for(i=3;i<=N;i++)
    {
        while(niv!=1&&det(v[st[niv-1]],v[st[niv]],v[i])<0)
        {
            niv--;
        }
        niv++;
        st[niv]=i;
    }
    st2[1]=N;
    st2[2]=N-1;
    niv2=2;
    for(i=N-2;i>=1;i--)
    {
        while(niv2!=1&&det(v[st2[niv2-1]],v[st2[niv2]],v[i])<0)
        {
            niv2--;
        }
        niv2++;
        st2[niv2]=i;
    }
    fout<<niv+niv2-2<<'\n';
    for(i=1;i<=niv;i++)
    {
        fout<<fixed<<setprecision(9)<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    }
    for(i=2;i<=niv2-1;i++)
    {
        fout<<fixed<<setprecision(9)<<v[st2[i]].x<<" "<<v[st2[i]].y<<'\n';
    }
}