Cod sursa(job #1547467)

Utilizator tudormaximTudor Maxim tudormaxim Data 9 decembrie 2015 16:53:24
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int nmax = 120005;
struct point {double x, y;} v[nmax];

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

inline bool cmp(point a, point b)
{
    return sarrus(v[1], a, b) > 0;
}

int main()
{
    ifstream fin ("infasuratoare.in");
    ofstream fout ("infasuratoare.out");
    ios_base::sync_with_stdio(false);
    int n, i, st[nmax], top=0, poz=1;
    fin >> n;
    for(i=1; i<=n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if(v[i].x < v[poz].x) poz=i;
        if(v[i].x == v[poz].x && v[i].y < v[poz].y) poz=i;
    }
    swap(v[1], v[poz]);
    sort(v+2, v+n+1, cmp);
    v[n+1]=v[1];
    st[++top]=1;
    for(i=2; i<=n; i++)
    {
        st[++top]=i;
        while(sarrus(v[st[top-1]], v[st[top]], v[i+1]) < 0) top--;
    }
    fout << setprecision(6) << fixed << top << "\n";
    for(i=1; i<=top; i++)
        fout << v[st[i]].x << " " << v[st[i]].y << "\n";
    fin.close();
    fout.close();
    return 0;
}