Cod sursa(job #1279463)

Utilizator dr_personalityEftime Andrei Horatiu dr_personality Data 30 noiembrie 2014 13:54:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
 
struct punct{
    double x, y;
};
 
const int nmax = 120006;
int n, lst, pozfirst;
punct v[nmax], first, st[nmax];
 
double det(punct a,punct b,punct c)
{
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
 
bool compar(punct a, punct b)
{
    return (det(a, first, b)>0);
}
 
int main(){
    int player_unu=0;
 
    first.x = 100000000000;
    first.y = 100000000000;
 
    in>>n;
    for(int i = 0; i<n; i++)
    {
        in>>v[i].x>>v[i].y;
 
        if(v[i].x==first.x && v[i].y<first.y)
        {
            first = v[i];
            pozfirst = i;
        }
        if(v[i].x<first.x)
        {
            first = v[i];
            pozfirst = i;
        }
    }
 
    swap(v[pozfirst], v[0]);
    sort(v + 1, v + n, compar);
 
    st[0] = first;
    lst = 1;
 
    for(int i = 1; i<n; i++)
    {
        while(lst>1 && det(st[lst - 2], st[lst - 1], v[i])>=0)
            lst--;
 
        st[lst] = v[i];
        lst++;
    }
 
    out<<lst<<'\n';
    out<<setprecision(6)<<fixed;
    for(int i = 0; i<lst; i++)
        out<<st[i].x<<' '<<st[i].y<<'\n';
 
    return player_unu;
}