Cod sursa(job #3288354)

Utilizator Tudor28Ceclan Tudor Tudor28 Data 21 martie 2025 18:18:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define oo 1000000000
struct punct
{
    double x;
    double y;
} v[120005];
bool smaller(punct x, punct y)
{
    if (x.y < y.y)
    {
        return true;
    }
    if (x.y == y.y)
    {
        return x.x < y.x;
    }
    return false;
}
double distance(punct a, punct b)
{
    return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}
int orientation(punct a, punct b, punct c)
{
    // diferenta dintre panta dreptelor
    // c.y-b.y/c.x-b.x - b.y-a.y/b.x-a.x
    int d = (c.y - b.y) * (b.x - a.x) - (b.y - a.y) * (c.x - b.x);
    if (d > 0)
        return 1;
    if (d < 0)
        return -1;
    // d==0
    return 0;
}
double angle(punct a, punct b)
{
    return atan2(b.y - a.y, b.x - a.x);
}
bool cmp(punct a, punct b)
{
    return angle(v[0], a) < angle(v[0], b);
}
int main()
{

    // cout << angle({0, 0}, {1, 1});
    int n;
    fin >> n;
    punct start;
    int istart;

    start.x = oo;
    start.y = oo;
    for (int i = 0; i < n; i++)
    {

        fin >> v[i].x >> v[i].y;
        if (smaller(v[i], start))
        {
            start = v[i];
            istart = i;
        }
    }
    swap(v[istart], v[0]);
    sort(v + 1, v + n, cmp);
    // for (int i = 0; i < n; i++)
    // {
    //     fout << v[i].x << " " << v[i].y << '\n';
    // }
    vector<int> ras;
    ras.push_back(0);
    int size = 1;
    for (int i = 1; i < n; i++)
    {
        if (ras.size() > 2 && orientation(v[ras[ras.size() - 2]], v[ras[ras.size() - 1]], v[i]) != 1)
        {
            ras.erase(ras.begin() + ras.size() - 1);
        }
        ras.push_back(i);
    }
    fout << ras.size() << '\n';
    for (auto i : ras)
    {
        fout << v[i].x << " " << v[i].y << '\n';
    }
    return 0;
}