Cod sursa(job #2988469)

Utilizator Luka77Anastase Luca George Luka77 Data 4 martie 2023 17:47:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point
{
    double x, y;
};

const int NMAX = 120005;
int n;
int pozrez[NMAX];
point arr[NMAX];

inline double det(point a, point b, point c)
{
    return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y);
}

inline bool Trig(const point &a, const point &b)
{
    return det(arr[1], a, b) > 0;
}

inline void solution()
{
    int minipos = 1;
    double miniY = arr[1].y;

    for(int i = 1; i <= n; ++ i)
        if(miniY > arr[i].y)
        {
            miniY = arr[i].y;
            minipos = i;
        }

    swap(arr[1], arr[minipos]);

    sort(arr + 2, arr + n + 1,   Trig);

    int k = 2;
    pozrez[1] = 1;
    pozrez[2] = 2;

    for(int i = 3; i <= n; ++ i)
    {
        while(k > 1 && det(arr[pozrez[k - 1]], arr[pozrez[k]], arr[i]) <= 0)
            k--;
        pozrez[++k] = i;
    }

    fout << k << '\n';

    for(int i = 1; i <= k; ++ i)
    {
        fout << fixed << setprecision(12) << arr[pozrez[i]].x << ' ' << arr[pozrez[i]].y << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> n;

    for(int i = 1; i <= n; ++ i)
        fin >> arr[i].x >> arr[i].y;

    solution();

    return 0;
}