Cod sursa(job #1609089)

Utilizator Bot32King Max Bot32 Data 22 februarie 2016 16:49:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

#define nrmax 120001

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct punct
{
    double x , y;
}v[nrmax] , sol[nrmax];

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

bool comp ( punct a , punct b )
{
    return panta(v[1],a,b) > 0;
}

int n ;

int main()
{
    f >> n;
    int poz = 1;
    for ( int i = 1; i <= n ; i++ )
    {
        f >> v[i].x >> v[i].y ;
        if ( v[i].x < v[poz].x or ( v[i].x == v[poz].x and v[i].y < v[poz].y ) )
            poz = i;
    }
    swap(v[1],v[poz]);
    sort ( v+2 , v+n+1 , comp) ;
    int top = 2;
    sol[1] = v[1];
    sol[2] = v[2];
    for ( int i = 3; i <= n; i++ )
    {
        while ( top >= 2 and panta(sol[top-1],sol[top],v[i]) < 0 ) top--;
        sol[++top] = v[i];
    }
    g << top << "\n";
    for ( int i = top; i ; i-- )
        g <<fixed <<setprecision(9) << sol[i].x << " " << sol[i].y << "\n" ;
    return 0;
}