Cod sursa(job #2287598)

Utilizator BurlacuMateiBurlacu Matei BurlacuMatei Data 22 noiembrie 2018 09:11:57
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <iomanip>
#define MAX 120100

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

int n;
int vf;

struct pt{
    double x, y;
}minim, p[MAX], st[MAX];

int pozmin;
double CP(pt a, pt b, pt c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
bool cmp(pt a, pt b)
{
    return CP(p[1], a, b) < 0;
}

bool m(pt a)
{
    if(a.x < minim.x) return 1;
    if(a.x == minim.x)
        if(a.y < minim.y) return 1;
    return 0;
}


int main()
{int i;

    minim.x = INT_MAX;
    minim.y = INT_MAX;

    fin >> n;
    for(i=1;i<=n;i++)
    {
        fin>>p[i].x;
        fin>>p[i].y;

        if(m(p[i]))
        {
            minim = p[i];
            pozmin = i;
        }
    }

    swap(p[1], p[pozmin]);
    sort(1 + p, 1 + p + n, cmp);

    /*for(i=1;i<=n;i++)
        fout<<p[i].x<<' '<<p[i].y<<'\n';*/

    vf = 2;

    st[1] = p[1];
    st[2] = p[2];

    for (int i = 3; i <= n; i++) {
        while (vf > 2 && CP(st[vf - 1], st[vf], p[i]) >= 0)
            vf--;
        st[++vf] = p[i];
    }

    fout << fixed;
    fout << setprecision(6);

    fout << vf << '\n';
    for (int i = 1; i <= vf; i++)
        fout << st[i].x << ' ' << st[i].y << '\n';
    return 0;
}