Cod sursa(job #2063097)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 11 noiembrie 2017 09:28:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>

using namespace std;

FILE * fin=fopen("infasuratoare.in","r");
FILE * fout=fopen("infasuratoare.out","w");

struct punct
{
    double x,y;
};

int n;
punct sol[120005];

inline double prodIncrucisat(punct A, punct B, punct C)
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool comp(punct a, punct b)
{
    return prodIncrucisat(sol[1],a,b) < 0;
}

void infasuratoare(punct*v, int n);

int main()
{
    int i;

    fscanf(fin,"%d",&n);
    for (i=1;i<=n;i++)
        fscanf(fin,"%lf%lf",&sol[i].x,&sol[i].y);
    infasuratoare(sol,n);
    return 0;
}

void infasuratoare(punct*v, int n)
{
    int i, vf, poz;
    punct minim, S[120005];

    minim = v[1];
    poz = 1;
    for (i=2;i<=n;i++)
    {
        if (v[i].x < minim.x)
        {
            minim = v[i];
            poz = i;
        }
        else if (v[i].x == minim.x && v[i].y < minim.y)
        {
            minim = v[i];
            poz = i;
        }
    }
    swap(v[1],v[poz]);
    sort(v+2,v+1+n,comp);
    S[1] = v[1];
    S[2] = v[2];
    vf = 2;
    for (i=3;i<=n;i++)
    {
        while (vf >= 2 && prodIncrucisat(S[vf-1],S[vf],v[i]) > 0)
            vf--;
        S[++vf] = v[i];
    }
    fprintf(fout,"%d\n",vf);
    for (i=vf;i>=1;i--)
        fprintf(fout,"%.6lf %.6lf\n",S[i].x,S[i].y);
}