Cod sursa(job #1690199)

Utilizator tudormaximTudor Maxim tudormaxim Data 14 aprilie 2016 21:12:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

const int nmax = 12e4;
struct point {double x, y;} p[nmax];

inline double sarrus(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;
}

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

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