Cod sursa(job #2924350)

Utilizator lolismekAlex Jerpelea lolismek Data 30 septembrie 2022 12:51:53
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

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

const int N = 120000;

struct Point{
	double x, y;
}v[N + 1];
	
namespace Geometry{
	double dist(Point p1, Point p2){
		double dx = p1.x - p2.x, dy = p1.y - p2.y;
		return sqrt(dx * dx + dy * dy);
	}
 
	double area(Point p1, Point p2, Point p3){
		return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
	}

	bool cmp(Point a, Point b){
		if(a.x == b.x)
			return a.y < b.y;
		return a.x < b.x;
	}

	// credit Toma Ariciu ca s inapt
	vector <Point> convexHull(Point v[], int n){
		sort(v + 1, v + n + 1, cmp);

		vector <Point> up, down;
		up.push_back(v[1]);
		down.push_back(v[1]);

		for(int i = 2; i <= n; i++){
			while((int)up.size() > 1 && area(up[(int)up.size() - 2], up[(int)up.size() - 1], v[i]) >= 0)
				up.pop_back();
			up.push_back(v[i]);
			while((int)down.size() > 1 && area(down[(int)down.size() - 2], down[(int)down.size() - 1], v[i]) <= 0)
				down.pop_back();
			down.push_back(v[i]);
		}
		
		vector <Point> CH = up;

		for(int i = (int)down.size() - 2; i >= 1; i--)
			CH.push_back(down[i]);

		reverse(CH.begin(), CH.end());

		return CH;
	}
}

int main(){

	int n;
	fin >> n;

	for(int i = 1; i <= n; i++)
		fin >> v[i].x >> v[i].y;

	vector <Point> CH = Geometry::convexHull(v, n);

	fout << fixed << setprecision(12);

	fout << (int)CH.size() << '\n';
	for(auto p : CH)
		fout << p.x << ' ' << p.y << '\n';

	return 0;
}