Cod sursa(job #1519975)

Utilizator UMihneaUngureanu Mihnea UMihnea Data 8 noiembrie 2015 10:39:14
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define punct pair<double, double>
using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

punct P[120010];
int n, i, t;
double X, Y;
bool crit_unghi(punct, punct);
double det(punct, punct, punct);

int main()
{
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>X>>Y;
        P[i] = make_pair(X, Y);
    }
    for(i=1;i<n;i++)
        if(P[i]<P[0])
            swap(P[i], P[0]);
    sort(P+1, P+n, crit_unghi);
    t=1;
    for(i=2;i<n;i++)
    {
        while(det(P[t-1], P[t], P[i]) < 0)
            t--;
        P[++t]=P[i];
    }
    g<<t+1<<'\n';
    for(i=0;i<=t;i++)
        g<<fixed<<setprecision(6)<<P[i].x<<' '<<P[i].y<<'\n';
    return 0;
}
bool crit_unghi(punct A, punct B)
{
    return det(P[0], A, B) > 0.0;
}
double det(punct A, punct B, punct C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y-(A.y*B.x+B.y*C.x+C.y*A.x);
}