Cod sursa(job #2659594)

Utilizator victorv88Veltan Victor victorv88 Data 17 octombrie 2020 10:51:08
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <cmath>

#include <fstream>

#include <vector>

#include <iomanip>

#include <algorithm>

#define EPSILON 0.0000001

using namespace std;



ifstream f("infasuratoare.in");

ofstream g("infasuratoare.out");



struct point

{

    double x, y;





};



int n;

point a[120005];

vector<point> v1, v2;



bool cmp(point a, point b)

{

    if(a.x < b.x)

        return true;

    if(abs(a.x - b.x) < EPSILON)

        return a.y < b.y;

}



double directie(point a, point b, point c)

{

    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);

}



void citire()

{

    f>>n;

    int pctmin = 0;

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

    {

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

    }

    sort(a, a+n, cmp);

}



void rezolvare()

{

    v1.push_back(a[0]);

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

    {

        while(v1.size() > 1 && directie(v1[v1.size()-2], v1[v1.size()-1], a[i]) > 0)

        {

            v1.pop_back();

        }

        v1.push_back(a[i]);

    }

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

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

    {

        while(v2.size() > 1 && directie(v2[v2.size()-2], v2[v2.size()-1], a[i]) > 0)

        {

            v2.pop_back();

        }

        v2.push_back(a[i]);

    }

}



void afisare()

{

    g<<v1.size() + v2.size() - 2<<"\n";

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

    {

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

    }

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

    {

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

    }

}



int main()

{

    citire();

    rezolvare();

    afisare();

    return 0;

}