Cod sursa(job #2650067)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 17 septembrie 2020 13:54:45
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>

using namespace std;

typedef long double ld;

struct point
{
    ld x;
    ld y;
};

ld f(point a, point b)
{
    return (a.x - b.x) * (a.y + b.y);
}

ld f(point a, point b, point c)
{
    return f(a, b) + f(b, c) + f(c, a);
}

int g(point a, point b, point c)
{
    ld v = f(a, b, c);
    if (v == 0)
    {
        return 0;
    }
    if (v > 0)
    {
        return +1;
    }
    else
    {
        return -1;
    }
}

point min(point a, point b)
{
    if (a.x < b.x)
    {
        return a;
    }
    if (b.x < a.x)
    {
        return b;
    }
    if (a.y < b.y)
    {
        return a;
    }
    else
    {
        return b;
    }
}


const int N = 120000 + 7;
int n;
int top;
point p[N];
point stk[N];

bool operator < (point a, point b)
{
    return g(p[1], a, b) > 0;
}

int main()
{
    freopen ("infasuratoare.in", "r", stdin);
    freopen ("infasuratoare.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].x >> p[i].y;
    }
    for (int i = 2; i <= n; i++)
    {
        if (p[i] < p[1])
        {
            swap(p[1], p[i]);
        }
    }
    sort(p + 2, p + n + 1);
    p[n + 1] = p[1];
    for (int i = 1; i <= n + 1; i++)
    {
        while (top >= 2 && g(stk[top - 1], stk[top], p[i]) <= 0)
        {
            top--;
        }
        stk[++top] = p[i];
    }
    top--;
    cout << top << "\n";
    for (int i = 1; i <= top; i++)
    {
        cout << fixed << setprecision(12) << stk[i].x << " " << stk[i].y << "\n";
    }
}