Cod sursa(job #2697798)

Utilizator AndreiAlexandru2k3Ciucan Andrei Alexandru AndreiAlexandru2k3 Data 19 ianuarie 2021 17:55:18
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

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

struct Punct
{
    double x, y;
};
Punct P[120002], St[120002];

int N, H;

void afis()
{
    g << H << '\n';
    g << fixed << setprecision(6);
    for(int i = 1; i <= H; i++)
        g << St[i].x << ' ' << St[i].y << '\n';
}

void swap(Punct &A, Punct &B)
{
    Punct aux = A;
    A = B;
    B = aux;
}

inline double patrat(double x)
{
    return x * x;
}

double distp(const Punct &A, const Punct &B)
{
    return patrat(A.x - B.x) + patrat(A.y - B.y);
}

bool compy(const Punct &A, const Punct &B)
{
    if(A.y == B.y)
        return A.x < B.x;
    return A.y < B.y;
}

double det(const Punct &A, const Punct &B, const Punct &C)
{
    return (double)(A.x - B.x) * (B.y - C.y) - (double)(A.y - B.y) * (B.x - C.x);
}

bool compd(const Punct &A, const Punct &B)
{
    double dd = det(P[1], A, B);
    if(dd == 0)
        return distp(P[1], A) < distp(P[1], B);
    return dd > 0;
}

int main()
{
    f >> N;
    int pmin = 1;
    for(int i = 1; i <= N; i++)
    {
        f >> P[i].x >> P[i].y;
        if(compy(P[i], P[pmin]))
            pmin = i;
    }
    swap(P[pmin], P[1]);
    sort(P + 2, P + N + 1, compd);
    St[1] = P[1];
    St[2] = P[2];
    H = 2;
    P[N + 1] = P[1];
    for(int i = 3; i <= N + 1; i++)
    {
        while(H >= 2 && det(St[H - 1], St[H], P[i]) < 0)
            H--;
        St[++H] = P[i];
    }
    H--;
    afis();
    return 0;
}