Cod sursa(job #1910921)

Utilizator tqmiSzasz Tamas tqmi Data 7 martie 2017 18:48:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int Nmax=120005,oo=1<<30;
int N,PI,ind[Nmax],St[Nmax];
double X[Nmax],Y[Nmax];

bool comp(int a,int b)
{
    return (double)(X[a]-X[PI])*(Y[b]-Y[PI])<(double)(X[b]-X[PI])*(Y[a]-Y[PI]);
}

long double semn(int a,int b,int c)
{
    return (long double)X[a]*Y[b]-X[b]*Y[a]+X[b]*Y[c]-X[c]*Y[b]+X[c]*Y[a]-X[a]*Y[c];
}

void read()
{
    fin>>N;
    X[0]=Y[0]=oo;
    for(int i=1;i<=N;i++)
    {
        fin>>X[i]>>Y[i];
        if(X[i]<X[PI] || (X[i]==X[PI] && Y[i]<Y[PI])) PI=i;
    }
    for(int i=1;i<=N;i++)
    {
        if(i!=PI)
        ind[++ind[0]]=i;
    }
    sort(ind+1,ind+ind[0]+1,comp);
    St[++St[0]]=PI;
    for(int i=1;i<=ind[0];i++)
    {
        if(ind[i]!=PI)
        {
            while(St[0]>2 && semn(St[St[0]-1],St[St[0]],ind[i])>0)
                St[0]--;
            St[++St[0]]=ind[i];
        }
    }
    St[++St[0]]=PI;
    fout<<St[0]-1<<"\n";
    reverse(St+1,St+St[0]+1);
    for(int i=1;i<St[0];i++)
        fout<<fixed<<setprecision(6)<<X[St[i]]<<" "<<Y[St[i]]<<"\n";
}


int main()
{
    read();
    return 0;
}