Cod sursa(job #3270933)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 24 ianuarie 2025 21:24:45
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cmath>

using namespace std;
const int NMAX = 120002;
using ld = long double;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct puncte {
    ld x, y;
}v[NMAX], p0;

bool cmp(puncte a, puncte b) {
    ld unghia = atan2(a.y - p0.y, a.x - p0.x);
    ld unghib = atan2(b.y - p0.y, b.x - p0.x);
    if(unghia == unghib) {
        ld dista = (a.x - p0.x) * (a.x - p0.x) + (a.y - p0.y) * (a.y - p0.y);
        ld distb = (b.x - p0.x) * (b.x - p0.x) + (b.y - p0.y) * (b.y - p0.y);
        return dista < distb;
    }
    return unghia < unghib;
}
ld determ(puncte a, puncte b, puncte c) { ///aria triun
    return a.x * b.y + b.x * c.y + c.x * a.y -
           b.y * c.x - c.y * a.x - a.y * b.x;
}


vector <puncte> s;
int main()
{
    int n;
    p0 = {0, 0}; ///media aritm
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        p0.x += v[i].x;
        p0.y += v[i].y;
    }
    p0.x /= n;
    p0.y /= n;
    //cout << p0.x << " " << p0.y << '\n';
    sort(v + 1, v + n + 1, cmp);
    /*for(int i = 1; i <= n; i++)
        cout << v[i].x << " " << v[i].y << '\n';
    cout << '\n';*/
    s.push_back(v[1]);
    s.push_back(v[2]);
    for(int i = 3; i <= n; i++) {
        while(s.size() >= 2 && determ(s[s.size() - 2], s[s.size() - 1], v[i]) < 0) {
            s.pop_back();
        }
        s.push_back(v[i]);
        //cout << "yoo " << i << "  " << s.size() << '\n';
    }
    while(s.size() >= 2 & determ(s[s.size() - 2], s[s.size() - 1], s[0]) < 0)
        s.pop_back();
    cout << s.size() << '\n';
    for(auto var : s)
        cout << setprecision(12) << fixed << var.x << " " << var.y << '\n';
    return 0;
}