Cod sursa(job #3288345)

Utilizator Tudor28Ceclan Tudor Tudor28 Data 21 martie 2025 16:38:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 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.x < y.x)
    {
        return true;
    }
    if (x.x == y.x)
    {
        return x.y < y.y;
    }
    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;
}
int main()
{

    cout << orientation({0, 0}, {1, 1}, {2, 3});
    // punct a = {0, 0}, b = {1, -1};

    // cout << atan2(b.y - a.y, b.x - a.x) / 3.14 * 180;
    // return 0;
    int n;
    fin >> n;
    punct start;
    int istart;
    vector<int> ras;
    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;
        }
    }
    bool first = true;
    int cur = istart;
    cout << cur;
    while (first || istart != cur)
    {
        first = false;
        cout << cur << '\n';

        ras.push_back(cur);
        int nextPoint = cur;
        for (int i = 0; i < n; i++)
        {
            if (i == cur)
            {
                continue;
            }
            int o = orientation(v[cur], v[nextPoint], v[i]);
            // cout << o << " ";
            if (o == 1)
            {
                nextPoint = i;
            }
        }
        cur = nextPoint;
    }
    reverse(ras.begin(), ras.end());
    fout << ras.size() << '\n';
    for (auto i : ras)
    {
        fout << v[i].x << " " << v[i].y << '\n';
    }
    return 0;
}