Cod sursa(job #1882679)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 17 februarie 2017 13:40:27
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

#define NMAX 120001

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;

struct punct
{
    double x, y;
    friend istream& operator>>(istream &in,punct &p)
    {
        in>>p.x>>p.y;
        return in;
    }
    friend ostream& operator<<(ostream &out,punct &p)
    {
        out<<p.x<<' '<<p.y<<'\n';
        return out;
    }
}puncte[NMAX];

vector<punct> stiva;

punct most_left;
int most_left_index;

vector<punct> hull;

double det(punct a, punct b,punct c)
{
    return (a.x-b.x)*(b.y-c.y) - (a.y-b.y)*(b.x-c.x);
}

bool comparator(punct a,punct b)
{
    return det(a,b,most_left) < 0;
};

void citire()
{
    f>>n;

    f>>puncte[0];

    most_left=puncte[0];

    for(int i=1;i<n;i++)
    {
        f>>puncte[i];

        if(puncte[i].x<most_left.x)
        {
            most_left = puncte[i];
            most_left_index = i;
        }
    }
    hull.push_back(most_left);

    swap(puncte[most_left_index],puncte[0]);

    sort(puncte+1,puncte+n+1,comparator);

    stiva.push_back(puncte[0]);
    stiva.push_back(puncte[1]);
}

punct first()
{
    return stiva[stiva.size()-1];
}

punct second()
{
    return stiva[stiva.size()-2];
}
void infasuratoare()
{
    for (int i = 2; i < n; i++) {
        while (stiva.size() >= 2 && det(second(), first(), puncte[i]) > 0)
            stiva.pop_back();
        stiva.push_back(puncte[i]);
    }
    g<<stiva.size()<<'\n';
    g<<fixed;
    for (int i = stiva.size()-1; i >= 0; i--)
        g<<setprecision(9)<<stiva[i];
}

int main()
{
    citire();
    infasuratoare();

    return 0;
}