Cod sursa(job #2602194)

Utilizator TudorCristeaCristea Tudor TudorCristea Data 16 aprilie 2020 10:42:21
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

#define INF 0x3f3f3f3f

struct punct
{
    double x,y;
}P[120005],stiva[120005],minim;

double determinant (punct A,punct B,punct C)
{
    B.x-=A.x;
    B.y-=A.y;
    C.x-=A.x;
    C.y-=A.y;
    double produs=B.x*C.y-B.y*C.x;
    return produs;
}

bool cmp (punct A,punct B)
{
    return (determinant(P[1],A,B)<0);
}

int N;

int main()
{
    fin >> N;
    minim.x=minim.y=INF;
    int start;
    int i;
    for (i=1;i<=N;++i)
    {
        fin >> P[i].x >> P[i].y;
        if (P[i].x<minim.x)
        {
            minim=P[i];
            start=i;
        }
        else if (P[i].x==minim.x && P[i].y<minim.y)
        {
            minim.y=P[i].y;
            start=i;
        }
    }
    punct aux=P[1];
    P[1]=P[start];
    P[start]=aux;
    sort(P+2,P+N+1,cmp);
    stiva[1]=P[1];
    stiva[2]=P[2];
    int M=2;
    for (i=3;i<=N;++i)
    {
        while (M>=2 && determinant(stiva[M-1],stiva[M],P[i])>0)
        {
            --M;
        }
        ++M;
        stiva[M]=P[i];
    }
    fout << M << '\n';
    for (i=M;i>=1;--i)
    {
        fout << setprecision(12) << fixed << stiva[i].x << " " << stiva[i].y << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}