Cod sursa(job #2280013)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 10 noiembrie 2018 10:59:58
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

struct punct
{
    double x, y;
};

int n, pozmin, vf;
double minim=1000000001;
punct S[120005], p[120005];

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

bool comp(punct A, punct B)
{
    double xa, ya, xb, yb, t1, t2, r1, r2;

    xa = A.x-p[1].x;
    ya = A.y-p[1].y;
    xb = B.x-p[1].x;
    yb = B.y-p[1].y;
    if (xa == 0 && xb == 0)
    {
        if (ya*yb < 0)
            return ya<yb;
        return ya*ya<yb*yb;
    }
    if (xa == 0 && ya < 0)
        return 1;
    if (xa == 0 && ya > 0)
        return 0;
    if (xb == 0 && yb < 0)
        return 0;
    if (xb == 0 && yb > 0)
        return 1;
    t1 = ya/xa;
    t2 = yb/xb;
    if (modul(t1-t2) < 0.000000001)
    {
        r1 = xa*xa+ya*ya;
        r2 = xb*xb+yb*yb;
        return r1 < r2;
    }
    return t1 < t2;
}

int main()
{
    int i;

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