Cod sursa(job #1393166)

Utilizator Arodoet96Teodora Stoleru Arodoet96 Data 19 martie 2015 09:53:37
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define DMAX 120004

using namespace std;

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

int n;
struct punct
{
    double x, y;
}
P[DMAX];
int p0;
int infasuratoare[DMAX], inf;

void citire();
bool cmp(const punct &a, const punct &b);
double produs(punct a, punct b, punct c);
void infasuratoare_convexa();
void afisare();

int main()
{
    citire();
    sort(P+2, P+n+1, cmp);
    infasuratoare_convexa();
    afisare();
    return 0;
}

void citire()
{
    int i;
    punct aux;

    fin>>n>>P[1].x>>P[1].y;
    p0=1;
    for(i=2;i<=n;++i)
    {
        fin>>P[i].x>>P[i].y;
        if(P[i].x<P[p0].x || P[i].x==P[p0].x && P[i].y<P[p0].y)
            p0=i;
    }

    aux=P[1];
    P[1]=P[p0];
    P[p0]=aux;
}

bool cmp(const punct &a, const punct &b)
{
    return produs(P[1], a, b)>0;
}

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

void infasuratoare_convexa()
{
    int i;

    infasuratoare[1]=1; infasuratoare[2]=2; inf=2;

    for(i=3;i<=n;++i)
    {
        while(inf>=2 && produs(P[infasuratoare[inf-1]], P[infasuratoare[inf]], P[i])<=0)
            --inf;
        infasuratoare[++inf]=i;
    }
}

void afisare()
{
    int i;
    fout<<inf<<'\n';
    for(i=1;i<=inf;++i)
        fout<<fixed<<setprecision(12)<<P[infasuratoare[i]].x<<' '<<P[infasuratoare[i]].y<<'\n';
}