Cod sursa(job #2371389)

Utilizator AlexTudorAlex Brinza AlexTudor Data 6 martie 2019 17:25:05
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

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

const int NMAX=120005;

vector < int > S;

struct punct
{
    double x,y;
};

double X=1000000005,Y=1000000005;

int low,N;

punct A[NMAX];

int pula( punct A, punct B , punct C)
{
    long long rez=1LL*(A.y - B.y) * 1LL*(B.x-C.x) - 1LL*(B.y-C.y) * 1LL*(A.x-B.x);

    if( rez < 0 ) return 1;
    else  if(rez > 0 ) return -1;
          else return 0;
}

bool comp( punct C , punct B)
{
    return ( pula ( A[1], C , B) == 1 );
}

void read()
{
    fin>>N;

    for(int i=1;i<=N;++i)
        {
         fin>>A[i].x>>A[i].y;

         if(A[i].y<Y)
         {
             Y=A[i].y;
             X=A[i].x;
             low=i;
         }
         else
            if(A[i].y==Y && A[i].x<X)
                {
                 X=A[i].x;
                 low=i;
                }
        }

    swap(A[low],A[1]);

    sort(A+1,A+N+1,comp);

    S.push_back(1);
    S.push_back(2);

    for(int i=3;i<=N;++i)
    {
        while(pula( A[S[S.size()-2]] ,A[ S.back()  ], A[i]) < 0)
            S.pop_back();

        S.push_back(i);
    }

    fout<<S.size()<<"\n";

    for(int i=0;i<S.size();++i) fout<<fixed<<setprecision(6)<<A[S[i]].x<<" "<<A[S[i]].y<<"\n";

}

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