Cod sursa(job #3271259)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 25 ianuarie 2025 15:33:29
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <deque>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using db = long double;

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

struct punct{
    db x, y, rad; // radiani
};

db d1(punct a, punct b){
    return abs(a.x - b.x) * abs(a.x - b.x) + abs(a.y - b.y) * abs(a.y - b.y);
}

db det(punct a, punct b, punct c) {
    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;
}

punct p0;
bool cmp(punct a, punct b) {
    if(a.rad == b.rad) {
        db dista = (a.x - p0.x) * (a.x - p0.x) + (a.y - p0.y) * (a.y - p0.y);
        db distb = (b.x - p0.x) * (b.x - p0.x) + (b.y - p0.y) * (b.y - p0.y);
        return dista < distb;
    }
    return a.rad < b.rad;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; in >> n;
    punct v[n];

    for(int i = 0; i < n; i++){
        in >> v[i].x >> v[i].y;
        p0.x += v[i].x;
        p0.y += v[i].y;
    }

    p0.x /= n;
    p0.y /= n;

    // cout << "x0 = " << x0 << " y0 = " << y0 << '\n';

    for(int i = 0; i < n; i++){
        v[i].rad = atan2(v[i].y - p0.y, v[i].x - p0.x);
        // cout << "i = " << i << " v = " << v[i].x << " " << v[i].y << " rad = " << v[i].rad << '\n';
    }

    sort(v + 0, v + n, cmp);

    // cout << "v : \n";
    // for(int i = 0; i < n; i++){
    //     cout << v[i].x << " " << v[i].y << '\n';
    // }

    deque< punct > sol;
    for(int i = 0; i < n; i++){
        // cout << "Suntem la ( " << v[i].x << " , " << v[i].y << " )\n";
        while(sol.size() >= 2){
            punct a = sol[ sol.size() - 2 ];
            punct b = sol[ sol.size() - 1 ];

            if( det( a, b, v[i] ) < 0 ){
                // cout << " -- > Eliminam " << b.x << " , " << b.y << '\n';
                sol.pop_back();
            }else break;
        }
        sol.push_back(v[i]);
    }
    // out << sol.size() << '\n';
    // for(int i = 0; i < sol.size(); i++){
    //     out << fixed << setprecision(6) << sol[i].x << " " << sol[i].y << '\n';
    // }

    int l = 0, sz = sol.size();
    while(sol.size() > 3){
        if( det( sol[sol.size() - 2], sol[sol.size() - 1], sol[l] ) < 0 ){
            sol.pop_back();
            sz--;
        }else if(det(sol[sol.size() - 1], sol[l], sol[l + 1]) < 0){
            l++;
            sz--;
        }else break;
    }

    out << sz << '\n';
    for(int i = l; i < sol.size(); i++){
        out << fixed << setprecision(12) << sol[i].x << " " << sol[i].y << '\n';
    }
    
    return 0;
}