Cod sursa(job #2339485)

Utilizator DavidLDavid Lauran DavidL Data 8 februarie 2019 23:14:22
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");

const int NMAX = 120005;

struct punct
{
    long double x, y;
};

bool operator <(const punct &a, const punct &b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int n;
punct P[NMAX], zeu;
punct stiva[NMAX];
int k;

long double dist(punct A, punct B)
{
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

long double unghi(punct A, punct B)
{
    if (B.y < A.y)
        return (B.x - A.x) / dist(A, B);
    else
        return 1 + (B.y - A.y) / dist(A, B);
}

bool grhm(punct A, punct B)
{
    if (A.x == zeu.x && A.y == zeu.y)
        return 1;
    if (B.x == zeu.x && B.y == zeu.y)
        return 0;
    return unghi(zeu, A) > unghi(zeu, B);
}

int verifica(punct A, punct B, punct C)
{
    return A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y);
}

int main()
{
    fi >> n;
    zeu.x = zeu.y = 1e10;
    for (int i = 1; i <= n; i++)
    {
        fi >> P[i].x >> P[i].y;
        zeu = min(zeu, P[i]);
    }
    sort(P + 1, P + n + 1, grhm);

    stiva[++k] = P[1];

    for (int i = 2; i <= n; i++)
    {
        while (k > 1 && verifica(stiva[k - 1], stiva[k], P[i]) > 0)
            k--;
        stiva[++k] = P[i];
    }

    fo << k << "\n";
    for (int i = k; i >= 1; i--)
        fo << fixed << setprecision(20) << stiva[i].x << " " << stiva[i].y << "\n";

    return 0;
}