Cod sursa(job #2978861)

Utilizator sLinXDinca Robert sLinX Data 14 februarie 2023 16:19:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>

#define x first
#define y second

using namespace std ;

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

typedef pair<double,double> Point;
Point Points[120005], S[120005];

int n;
int head ;


void ReadFile()
{
    fin >> n ;
    for(int i = 1; i <= n ;++i)
        {
            fin >> Points[i].x >> Points[i].y;
        }
}

inline double Prod_Incrucisat(const Point& A, const Point& B, const Point& C )
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

inline int cmp(const Point& P1,const Point& P2)
{
    return (Prod_Incrucisat(Points[1], P1, P2) < 0);
}

void Sortare()
{
    int pos = 1;
    for(int i = 2; i<= n; ++i)
            if(Points[i] < Points[pos])
                pos = i;
        swap(Points[1], Points[pos]);
        sort(Points+2, Points+n+1, cmp);



}


void ScanareGraham()
{
    Sortare();

    S[1] = Points[1];
    S[2] = Points[2];

    head = 2;
    for(int i = 3; i <= n ; ++i)
        {
            while(head >= 2 && Prod_Incrucisat(S[head-1], S[head], Points[i]) > 0)
                --head;
            S[++head] = Points[i];

        }


}


void Afisare()
{
    fout << fixed ;
    fout << head << '\n';
    for(int i = head ; i>=1; i--)
        fout << setprecision(9) << S[i].x << ' ' << S[i].y << '\n';


}

int main()
{
    ReadFile();
    ScanareGraham();
    Afisare();

    return 0;
}