Cod sursa(job #2116230)

Utilizator FredyLup Lucia Fredy Data 27 ianuarie 2018 13:45:38
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;

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

#define lim 120010
struct pct {double x,y;} ini[lim];
int sol[lim];
int minm(1), n, dr;

double det (pct A, pct B, pct C)
{
    double rez = A.x*B.y + B.x*C.y + A.y*C.x - C.x*B.y - B.x*A.y - A.x*C.y;
    return rez;
}

bool cmp (pct A, pct B)
{
    return det (ini[1], A, B) >= 0;
}

int main()
{
    fin>>n;
    for (int i=1; i<=n; i++)
    {
        fin>>ini[i].x>>ini[i].y;
        if (ini[i].x < ini[minm].x) minm=i;
        else if (ini[i].x==ini[minm].x && ini[i].y<ini[minm].y)  minm=i;
    }

    swap (ini[1], ini[minm]);
    sort (ini+2, ini+n+1, cmp);

    dr=0;
    for (int i=1; i<=n; i++)
    {
        while (dr>1 && det(ini[sol[dr-1]], ini[sol[dr]], ini[i]) < 0)  dr--;
        sol[++dr]=i;
    }

    fout<<dr<<'\n';
    for (int i=1; i<=dr; i++)
        fout<<fixed<<ini[sol[i]].x<<' '<<ini[sol[i]].y<<'\n';

    return 0;
}