Cod sursa(job #2873262)

Utilizator AlexNeaguAlexandru AlexNeagu Data 19 martie 2022 00:22:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
	
#include <bits/stdc++.h>
using namespace std;
#define int long long 
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
	double x, y;
	void read() {
		in >> x >> y;
	}
	void write() {
		out << fixed << setprecision(12) << x << ' ' << y << '\n';
	}
	point operator - (const point &B) const {
		return point{x - B.x, y - B.y};
	}
	void operator -= (const point &B) {
		x -= B.x;
		y -= B.y;
	}
	long double operator * (const point &B) const {
		return x * B.y - y * B.x;
	}
	long double orientation(const point &A, const point &B) const {
		return (A - *this) * (B - *this);
	}
	long double dist(point A) {
		A -= *this;
		return A.x * A.x + A.y * A.y;
	}
	bool operator <(const point &A) {
		if(x == A.x) {
			return y < A.y;
		}
		return x < A.x;
	}
		
};
vector<point> buildHull(vector<point> A) {
	// 
	vector<point> hull;
	for(int i = 0; i < (int) A.size(); ++i) {
		while(hull.size() >= 2) {
			int sz = hull.size();
			point P1 = hull[sz - 2];
			point P2 = hull[sz - 1];
			if(P2.orientation(P1, A[i]) < 0) {
				break;
			}
			hull.pop_back(); 
		}
		hull.push_back(A[i]);
	}
	return hull;
}
 
int32_t main() {
	
	int n;
	in >> n;
	vector<point> points(n);
	for(int i = 0; i < n; ++i) {
		points[i].read();
	}
	
	sort(points.begin(), points.end());
	vector<point> upperHull = buildHull(points);
	reverse(points.begin(), points.end());
	vector<point> lowerHull = buildHull(points);
	
	upperHull.pop_back();
	lowerHull.pop_back();
	out << upperHull.size() + lowerHull.size() << '\n';
	
	for(auto it : upperHull) {
		it.write();
	}
	for(auto it : lowerHull) {
		it.write();
	}
	
}