Cod sursa(job #2015731)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 27 august 2017 11:18:33
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#define nmax 120005
#include <iomanip>
using namespace std;
fstream f1("infasuratoare.in", ios::in);
fstream f2("infasuratoare.out", ios::out);
struct punct
{
    double x, y;
}p[nmax], aux, stiva[nmax];
long int n, vf;
void citire()
{
    long int i, poz;
    f1>>n;
    for(i=1; i<=n; i++)
        f1>>p[i].x>>p[i].y;

    poz=1;
    for(i=2; i<=n; i++)
        if((p[i].x< p[poz].x)||((p[i].x== p[poz].x)&&(p[i].y< p[poz].y))) poz=i;
    aux= p[1];
    p[1]=p[poz];
    p[poz]=aux;///p[1]= punct cu xmin
}
double crossp(punct p0, punct p1, punct p2)
{
    return ((p1.x- p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x));
}
void sortare()
{
    ///sortezi punctele trig comparandu-le 2 cate 2 in fct de produsul vectorial
    long int i, j, gap;
    for(gap=n/2; gap>=1; gap/=2)
        for(i=gap+1; i<=n; i++)
    {
        aux=p[i];
        for(j=i-gap; (j>=1)&&(crossp(p[1], p[j], aux)<0); j-=gap)
            p[j+gap]=p[j];
        p[j+gap]=aux;
    }
}
void graham()
{
    long int i;
    stiva[1]=p[1];
    stiva[2]=p[2];
    vf=2;
    for(i=3; i<=n; i++)
    {
        if(crossp(stiva[vf-1], stiva[vf], p[i])>0) {vf++; stiva[vf]=p[i];}
        else {stiva[vf]=p[i];}
    }
}
void afisare()
{
    long int i;
    f2<<vf<<"\n";
    for(i=1; i<=vf; i++)
        f2<<fixed<<setprecision(9)<<stiva[i].x<<' '<<stiva[i].y<<"\n";
}
int main()
{
   citire();
   sortare();
   graham();
   afisare();
   return 0;
}