Cod sursa(job #2659673)

Utilizator victorv88Veltan Victor victorv88 Data 17 octombrie 2020 11:58:07
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>

#include <vector>

#include <fstream>

#include <algorithm>

#include <iomanip>

using namespace std;

ifstream fin("infasuratoare.in");

ofstream fout("infasuratoare.out");

struct punct

{

    double x,y;

} a[120005];

int  n;

vector <punct > rez1;

vector <punct > rez2;


bool cmp(punct a, punct b)

{

    if (a.x==b.x)

        return a.y<b.y;

    return a.x<b.x;

}

void citire()

{

    fin >> n;

    for( int i = 0; i < n; i++)

        fin >> a[i].x >> a[i].y;

}

int det(punct b,punct c,punct d)

{

    return b.x*c.y + c.x*d.y + b.y*d.x -c.x*b.y -d.x*c.y - b.x*d.y;

}

void solve1()

{

    sort(a,a + n,cmp);

    rez1.push_back(a[0]);

    rez1.push_back(a[1]);

    for(int i = 2; i < n; i++)

    {

        while(rez1.size() > 1 && det(rez1[rez1.size() - 2],rez1[rez1.size() - 1], a[i]) <= 0)

            rez1.pop_back();

            rez1.push_back(a[i]);

    }

}

void solve2()

{

    rez2.push_back(a[n - 1]);

    rez2.push_back(a[n - 2]);

    for(int i = n - 3; i >= 0; i--)

    {

        while(rez2.size() > 1 && det(rez2[rez2.size() - 2],rez2[rez2.size() - 1], a[i]) <= 0)

            rez2.pop_back();

        rez2.push_back(a[i]);



    }

}

void afisare()

{

    fout << rez1.size()+ rez2.size() - 2 << "\n";

    for( int i = 0; i < rez1.size() - 1 ;i++)

        fout <<fixed << setprecision(6) << rez1[i].x <<" " << rez1[i].y << "\n";

        for( int i = 0; i <= rez2.size() - 2 ;i++)

    fout <<fixed << setprecision(6) << rez2[i].x <<" " << rez2[i].y << "\n";

}

int main()

{

citire();

solve1();

solve2();

afisare();

    return 0;

}