Cod sursa(job #2170000)

Utilizator MaaaaaCristina Ma Maaaaa Data 14 martie 2018 20:28:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define nmax 120005
#define inf 1000000005
using namespace std;
fstream f1("infasuratoare.in", ios::in);
fstream f2("infasuratoare.out", ios::out);
int n, vf;
struct punct
{
    double x, y;
}p[nmax],  stiva[nmax];
double det(punct a, punct b, punct c)
{
    return (a.x*b.y+ b.x*c.y+ c.x*a.y- c.x*b.y - a.x*c.y- a.y*b.x);
}
bool cmp(punct a, punct b)
{
    return (det(p[1], a, b)>0);
}
void citire()
{
    int i, ind;
    double  xmin=inf, ymin=inf;
    f1>>n;
    for(i=1; i<=n; i++)
        f1>>p[i].x>>p[i].y;
    for(i=1; i<=n; i++)
        if((p[i].x< xmin)||((p[i].x==xmin)&&(p[i].y< ymin)))
    {
        xmin=p[i].x;
        ymin=p[i].y;
        ind=i;
    }
    swap(p[1], p[ind]);
    sort(p+2, p+n+1, cmp);
}
void graham()
{
    int i;
    vf=1; stiva[vf]=p[1];
    vf++; stiva[vf]=p[2];
    for(i=3; i<=n; i++)
    {
        while((vf>=2)&&(det(p[i], stiva[vf], stiva[vf-1])>0)) vf--;
        vf++; stiva[vf]=p[i];
    }
    f2<<vf<<"\n";
    for(i=1; i<=vf; i++)
        f2<<fixed<<setprecision(12)<<stiva[i].x<<' '<<stiva[i].y<<"\n";
}
int main()
{
    citire();
    graham();
    return 0;
}