Cod sursa(job #3309203)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 2 septembrie 2025 15:06:23
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include <bits/stdc++.h>

using namespace std;

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

using d64 = long double;
const d64 EPS = 1e-12;

struct Point {
    d64 x, y;
};

d64 cp(Point A, Point B, Point C) {
    return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}

int N;
vector<Point> P;

int main()
{
    fin >> N;
    P.resize(N);
    for(int i = 0; i < N; i++) {
        fin >> P[i].x >> P[i].y;
    }
    sort(P.begin(), P.end(), [](Point &a, Point &b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });
    
    vector<Point> hull;
    
    hull.push_back(P[0]);
    hull.push_back(P[1]);
    for(int i = 2; i < N; i++) {
        while(hull.size() >= 2 && cp(hull[hull.size() - 2], hull[hull.size() - 1], P[i]) <= EPS) {
            hull.pop_back();
        }
        hull.push_back(P[i]);
    }
    
    for(int i = N - 2; i >= 0; i--) {
        while(hull.size() >= 2 && cp(hull[hull.size() - 2], hull[hull.size() - 1], P[i]) <= EPS) {
            hull.pop_back();
        }
        hull.push_back(P[i]);
    }
    
    hull.pop_back();
    reverse(hull.begin(), hull.end());
    fout << hull.size() << "\n";
    for(int i = 0; i < hull.size(); i++) {
        fout << hull[i].x << " " << hull[i].y << "\n"; 
    }
    return 0;
}