Cod sursa(job #2650065)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 17 septembrie 2020 13:52:29
Problema Infasuratoare convexa Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 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 dist(point a, point b)
{
    ld dx = a.x - b.x;
    ld dy = a.y - b.y;
    return dx * dx + dy * dy;
}

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)
{
    int v = g(p[1], a, b);
    if (v == 0)
    {
        return dist(p[1], a) < dist(p[1], b);
    }
    else
    {
        return v > 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";
    }
}