Cod sursa(job #819317)

Utilizator danutbodbodnariuc danut danutbod Data 18 noiembrie 2012 20:11:48
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
#include <algorithm>
#define  Lmax 120003
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct Punct{
    double x,y;
};
Punct a[Lmax],stiva[Lmax];

bool cmp(Punct a, Punct b)
{
    if(a.y < b.y || (a.y == b.y && a.x < b.x)) return true;
    return false;
}
int semn(Punct a , Punct b, Punct c)
{
    if((b.x * c.y + a.x * b.y + c.x * a.y - a.y * b.x - c.x * b.y - a.x * c.y) >= 0)
        return 1;
    else
        return 0;
}
int n,i,k;
#include <iomanip>
int main()
{
    f>>n;
    for(i = 1; i <= n; i++)     f>>a[i].x>>a[i].y;
    sort(a + 1, a + n + 1, cmp);
    stiva[1]=a[1];
    k = 1;
    for(i = 2; i <= n; i++)
    {
        while(k > 1 && !semn(stiva[k-1], stiva[k], a[i])) k--;
        k++;
        stiva[k]=a[i];
    }
    for(i = n - 1; i >= 1; i--)
    {
        while(!semn(stiva[k-1], stiva[k], a[i]))k--;
        k++;
        stiva[k]=a[i];
    }
    g<<fixed; g<<setprecision(6);
    g<<k-1<<'\n';
    for(i = 1; i <= k-1 ; i++) g<< stiva[i].x <<" "<<stiva[i].y<<'\n';
    g.close();
    return 0;
}