Cod sursa(job #2659596)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 17 octombrie 2020 10:52:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 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;

    bool operator==(const point other) const
    {
        return x == other.x && y == other.y;
    }

    bool operator!=(const point other) const
    {
        return x != other.x || y != other.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;
    return false;
}

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;
}