Cod sursa(job #2685006)

Utilizator Robert.BrindeaBrindea Robert Robert.Brindea Data 15 decembrie 2020 17:01:06
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

const int MAXN = 120006;

struct Punct
{
    double x{0}, y{0};
    bool operator<(Punct term)
    {
        return x < term.x || (!(x < term.x) && y < term.y);
    }
};

int n;
Punct a[MAXN];
vector<Punct> s;

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

bool cmp(Punct x1, Punct x2)
{
    return det(a[0], x1, x2) < 0;
}

int main()
{
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> a[i].x >> a[i].y;
    int pos = 0;
    for(int i = 1; i < n; i++)
        if(a[i] < a[pos])
            pos = i;
    swap(a[0], a[pos]);
    sort(a+1, a+n, cmp);
    s.push_back(a[0]);
    for(int i = 1; i < n; i++)
    {
        while(s.size() >= 2 && det(s[s.size()-2], s[s.size()-1], a[i]) > 0) s.pop_back();
        s.push_back(a[i]);
    }
    fout << s.size() << "\n";
    for(int i = s.size()-1; i >= 0; i--)
        fout <<setprecision(15)<< s[i].x << " " << s[i].y << "\n";
    return 0;
}