Cod sursa(job #3348190)

Utilizator moloDaniMolodet Andrei Daniel moloDani Data 20 martie 2026 10:04:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <math.h>
#include <vector>
#include <iomanip>
#include <algorithm>

using namespace std;

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

const int mxN = 12e4 + 1;

struct pct{
    long double x, y;
};

int n, ind = 1;
pct p[mxN], pivot;
vector<pct> ans;

long double dis(pct a, pct b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// [xa, ya, 1]    [xa,     ya,   1]
// [xb, yb, 1] -> [xb-xa, yb-ya, 0]
// [xc, yc, 1]    [xc-xa, yc-ya, 0]

long double det(pct a, pct b, pct c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(pct a, pct b){
    long double unghi = det(pivot, a, b);
    if(unghi != 0) return unghi > 0;
    return dis(pivot, a) < dis(pivot, b);
}

int main(){
    int minim = 0;
    fin >> n;
    for(int i = 1; i <= n; i++){
        fin >> p[i].x >> p[i].y;
        if(minim == 0 || p[i].y < p[minim].y || (p[minim].y == p[i].y && p[i].x < p[minim].x))
            minim = i;
    }

    swap(p[1], p[minim]);
    pivot = p[1];

    sort(p + 2, p + 1 + n, cmp);

    ans = {p[1], p[2], p[3]};
    for(int i = 4; i <= n; i++){
        while(ans.size() >= 2 && det(ans[ans.size() - 2], ans[ans.size() - 1], p[i]) <= 0)
            ans.pop_back();
        ans.push_back(p[i]);
    }

    fout << ans.size() << "\n";
    for(auto x : ans){
        fout << fixed << setprecision(15) << x.x << " " << x.y << "\n";
    }
}