Cod sursa(job #2659568)

Utilizator razvanradulescuRadulescu Razvan razvanradulescu Data 17 octombrie 2020 09:49:25
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <vector>
#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> rez;

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;
        if(a[i].x < a[pctmin].x)
            pctmin = i;
    }
    rez.push_back(a[pctmin]);
}

void rezolvare()
{
    point referinta;
    if(rez[0] == a[0])
        referinta = a[1];
    else
        referinta = a[0];
    for(int i = 1; i<n; i++)
    {
        if(a[i] != referinta && a[i] != rez[0])
        {
            if(directie(rez[0], referinta, a[i]) < 0)
                referinta = a[i];
        }
    }
    rez.push_back(referinta);
    for(int j = 1; rez.back() != rez.front(); j++)
    {
        referinta = rez[0];
        for(int i = 1; i<n; i++)
        {
            if(a[i] != referinta && a[i] != rez[j])
            {
                if(directie(rez[j], referinta, a[i]) < 0)
                    referinta = a[i];
            }
        }
        rez.push_back(referinta);
    }
}

void afisare()
{
    g<<rez.size()-1<<"\n";
    for(int i = 0; i<rez.size()-1; i++)
    {
        g<<rez[i].x<<" "<<rez[i].y<<"\n";
    }
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}