Cod sursa(job #2756501)

Utilizator Stefan_GhinescuGhinescu Stefan-George Stefan_Ghinescu Data 1 iunie 2021 10:06:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#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;//aria = 0.5 * abs(suma de la i = 0 pana la n - 1 din det(xi xi+1 // yi yi+1))
    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;
}