Cod sursa(job #3197601)

Utilizator PetraPetra Hedesiu Petra Data 27 ianuarie 2024 10:42:24
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

#define NMAX 120003

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

struct punct {
    double x, y;
};

punct points[NMAX], leftPoint, st[NMAX];
int n, leftPointIndex, dr;

int det(punct a, punct b, punct c)
{
    return (a.x*b.y + b.x*c.y + a.y*c.x - b.y*c.x - a.y*b.x - c.y*a.x);
}

bool cmp(punct a, punct b)
{
    return det(leftPoint, a, b) >= 0;
}

int main()
{
    fin >> n;
    for (int i = 0; i < n; i++)
    {
        fin >> points[i].x >> points[i].y;
        if (points[i].x < points[leftPointIndex].x || (points[i].x == points[leftPointIndex].x && points[i].y < points[leftPointIndex].y))
            leftPointIndex = i;
    }

    swap(points[leftPointIndex], points[0]); // fixez punctul initial pe 0
    leftPoint = points[0];
    sort(points + 1, points + n, cmp);

    points[n] = points[0];
    st[++dr] = leftPoint; // == points[0]
    for (int i = 1; i <= n; i++)
    {
        while (det(st[dr-1], st[dr], points[i]) < 0)
            dr--;
        st[++dr] = points[i];
    }

    fout << dr << "\n";
    for (int i = 1; i <= dr; i++)
        fout << fixed << setprecision(12) << st[i].x << " " << st[i].y << "\n";
    return 0;
}