Cod sursa(job #2873096)

Utilizator AlexNeaguAlexandru AlexNeagu Data 18 martie 2022 17:26:10
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
// O(N ^ 2)
#include <bits/stdc++.h>
using namespace std;
#define int long long 

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

struct point {
	long 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;
	}
	int operator * (const point &B) const {
		return x * B.y - y * B.x;
	}
	int orientation(const point &A, const point &B) const {
		return (A - *this) * (B - *this);
	}
};
int32_t main() {
	
	int n;
	in >> n;
	vector<point> points(n);
	for(int i = 0; i < n; ++i) {
		points[i].read();
	}
	for(int i = 1; i < n; ++i) {
		if(points[i].x < points[0].x) {
			swap(points[0], points[i]);
		}
	}
	vector<point> hull;
	vector<bool> marked(n, false);
	int currentPoint = 0;
	while(!marked[currentPoint]) {
		marked[currentPoint] = true;
		hull.push_back(points[currentPoint]);
		int bestPoint = 0;
		if(!currentPoint) bestPoint = 1;
		for(int j = 0; j < n; ++j) {
			if(j != currentPoint && j != bestPoint) {
				if(points[currentPoint].orientation(points[j], points[bestPoint]) < 0) {
					bestPoint = j;
				}
			}
		}
		currentPoint = bestPoint;
	}
	out << hull.size() << '\n';
	for(point it : hull) {
		it.write();
	}
}