Cod sursa(job #3270053)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 21 ianuarie 2025 21:08:31
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <iomanip>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;
using db = double;

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

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

db arie(punct a, punct b, punct c){
    a.x -= c.x; b.x -= c.x;
    a.y -= c.y; b.y -= c.y;
    return (a.x * b.y - b.x * a.y);
}

bool cmp(punct a, punct b){
    if(a.rad != b.rad) return a.rad > b.rad;
    else if(a.x != b.x) return a.x > b.x;
    else return a.y > b.y;
}

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

    int n; in >> n;
    punct v[n];
    db x0 = 0, y0 = 0;

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

    // x0 /= n;
    // y0 /= n;

    for(int i = 0; i < n; i++){
        // v[i].x -= x0;
        // v[i].y -= y0;

        v[i].rad = atan2(v[i].x, v[i].y);
        // 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 + x0 << " " << v[i].y + y0 << '\n';
    // }

    vector< punct > sol;
    for(int i = 0; i < n; i++){
        while(sol.size() >= 2){
            punct a = sol[ sol.size() - 2 ];
            punct b = sol[ sol.size() - 1 ];

            if( arie( a, b, v[i] ) < 0 ){
                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 + x0 << " " << sol[i].y + y0 << '\n';
    }
    
    return 0;
}