Cod sursa(job #1568757)

Utilizator ArambasaVlad Arambasa Arambasa Data 14 ianuarie 2016 18:11:19
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int NMax = 120000;
pair <double,double> St[NMax + 5];
int N,Vf;
pair <double,double> P[NMax + 5];

void Read()
{
    fin>>N;
    for(int i =  1; i<=N; i++)
        {
            double x,y;
            fin >> x >> y;
            P[i] = make_pair(x,y);
        }
}

double Sign(pair<double,double> A,pair<double,double> B,pair<double,double> C)
{
    double S = A.first * B.second + B.first*C.second + C.first * A.second - A.second * B.first - B.second * C.first - C.second*A.first;
    return S;
}

bool Compare(pair<double,double> A,pair<double,double> B)
{
    return ( Sign(P[1], A, B) > 0);
}

void Solve()
{
    int PMin = 1;

    for(int i =  2; i <= N; i++)
        if ( (P[i].second < P[PMin].second) || (P[i].second == P[PMin].second && P[i].first < P[PMin].first))
            PMin = i;

    swap(P[1],P[PMin]);

    sort(P+2,P+N+1,Compare);

    St[1] = P[1]; St[2] = P[2]; Vf = 2;

    for(int i = 3; i<=N; i++)
        {
            while (Vf >=2 && Sign(St[Vf-1],St[Vf],P[i]) < 0)
                Vf--;
            St[++Vf] = P[i];
        }
}

void Print()
{
    fout<<Vf<<"\n";

    for(int i = 1; i<= Vf; i++)
        fout<<fixed<<setprecision(9)<<St[i].first<<" "<<St[i].second<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}