Cod sursa(job #2253920)

Utilizator AnDrEeA1915Monea Andreea AnDrEeA1915 Data 4 octombrie 2018 15:59:39
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define x first
#define y second
#define point pair<double,double>
#define nmax 200010

point v[nmax], a[nmax];
int n, nr;

double delta(point a, point b, point c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-(a.y*b.x+b.y*c.x+c.y*a.x);
}

int vf(const point p1,const point p2)
{
    return delta(v[1], p1, p2) > 0;
}

void convex()
{
    int poz = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(v[i] < v[poz])
          poz = i;
    }
    swap(v[1], v[poz]);
    sort(v+2, v+n+1, vf);
    a[1] = v[1];
    a[2] = v[2];
    nr = 2;
    for(int i = 3; i <= n; ++i)
    {
        while(delta(a[nr-1], a[nr], v[i])<=0)
            nr--;
        a[++nr] = v[i];
    }
}

int main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    convex();
    fout << nr << '\n';
    for(int i = 1; i <= nr; ++i)
    {
        fout << fixed << setprecision(6) << a[i].x <<' '<< a[i].y <<'\n';
    }
    return 0;
}