Cod sursa(job #2756510)

Utilizator VladdalVVasile Vlad Raul VladdalV Data 1 iunie 2021 10:35:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

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

const double eps=1.0e-14;
const double INF=1e9;
const int NMAX=120000;

struct POINT
{
	double x, y;
};

POINT P[NMAX+5], LL;
int h[NMAX+5];

double cp(const POINT& P1, const POINT& P2, const POINT& P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}

int ccw(const POINT& P1, const POINT& P2, const POINT& P3)
{
    double crossprod=cp(P1, P2, P3);
    if (fabs(crossprod)<eps)
        return 0;
    if (crossprod>=eps)
        return 1;
    return -1;
}

bool cmp(POINT& P1, POINT& P2)
{
    return ccw(LL, P1, P2)>0;
}

double arie_poligon(int n)
{
    double aria;
    int i;
    P[n]=P[0];
    aria=0;
    for (i=0; i<n; i++)
        aria=P[i].x*P[i+1].y-P[i+1].x*P[i].y;
    aria=0.5*fabs(aria);
    return aria;
}

using namespace std;

int main()
{
    int n, i, top;
    double a, b;
    fout<<fixed;
    fin>>n>>a>>b;
    P[0].x=a;
    P[0].y=b;
    for (i=1; i<n; i++)
    {
        fin>>a>>b;
        P[i].x=a;
        P[i].y=b;
        if (P[i].y-P[0].y<=-eps || ((fabs(P[i].y-P[0].y)<eps) && (P[i].x-P[0].x<=-eps)))
            swap(P[i], P[0]);
    }
    LL=P[0];
    P[n]=P[0];
    h[0]=0;
    h[1]=1;
    sort(P+1, P+n, cmp);
    top=1; i=2;
    while (i<=n)
    {
        if (ccw(P[h[top-1]], P[h[top]], P[i])>0)
        {
            h[++top]=i;
            i++;
        }
        else
        {
            --top;
        }
    }
    fout<<top<<'\n';
    for (i=0; i<top; i++)
        fout<<setprecision(6)<<P[h[i]].x<<' '<<setprecision(6)<<P[h[i]].y<<'\n';
    return 0;
}