Cod sursa(job #3309205)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 2 septembrie 2025 15:48:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 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> upper_hull;

	upper_hull.push_back(P[0]);
	upper_hull.push_back(P[1]);
	for(int i = 2; i < N; i++) {
		while(upper_hull.size() >= 2 && cp(upper_hull[upper_hull.size() - 2], upper_hull[upper_hull.size() - 1], P[i]) < EPS) {
			upper_hull.pop_back();
		}
		upper_hull.push_back(P[i]);
	}

	vector<Point> lower_hull;
	lower_hull.push_back(P[N - 1]);
	lower_hull.push_back(P[N - 2]);
	for(int i = N - 3; i >= 0; i--) {
		while(lower_hull.size() >= 2 && cp(lower_hull[lower_hull.size() - 2], lower_hull[lower_hull.size() - 1], P[i]) < EPS) {
			lower_hull.pop_back();
		}
		lower_hull.push_back(P[i]);
	}

	reverse(lower_hull.begin(), lower_hull.end());
	reverse(upper_hull.begin(), upper_hull.end());
	lower_hull.pop_back();
	upper_hull.pop_back();

	vector<Point> hull = lower_hull;
	hull.insert(hull.end(), upper_hull.begin(), upper_hull.end());
	fout << hull.size() << "\n";
	fout << fixed;
	for(int i = 0; i < hull.size(); i++) {
		fout << setprecision(12) << hull[i].x << " " << hull[i].y << "\n";
	}
	return 0;
}