Cod sursa(job #2907475)

Utilizator AswVwsACamburu Luca AswVwsA Data 30 mai 2022 14:09:20
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
struct pct
{
    double x, y;
} v[120002];

pct low;
double cross(pct a, pct b, pct c)
{
    return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}
bool cmp(pct a, pct b)
{
    return cross(a, b, low) > 0;
}

int st[120002];
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n, i;
    cin >> n;
    low.y = 1000000003;
    for (i = 1; i <= n; i++)
    {
        cin >> v[i].x >> v[i].y;
        if (v[i].y < low.y)
            low = v[i];
        else if (v[i].y == low.y and v[i].x < low.x)
            low = v[i];
    }
    sort(v + 2, v + n + 1, cmp);
    st[1] = 1;
    st[2] = 2;
    int top = 2;
    i = 3;
    while (i <= n)
    {
        if (cross(v[i], v[st[top]], v[st[top - 1]]) < 0)
        {
            st[++top] = i;
            i++;
        }
        else
            top--;
    }
    cout << top << "\n";
    for (i = 1; i <= top; i++)
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
}