Cod sursa(job #2833446)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 15 ianuarie 2022 11:10:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

struct Point {
	double x, y;
};

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

double angle(Point a, Point b) {
	return atan2(b.y - a.y, b.x - a.x);
}

int main() {
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
	int n;
	cin >> n;
	vector<Point> v;
	for(int i = 1; i <= n; i++) {
		double x, y;
		cin >> x >> y;
		v.push_back({x,y});
	}
	sort(v.begin(),v.end(),cmp);
	
	vector<Point> Upper;
	vector<Point> Lower;
	Upper.push_back(v[0]);
	Lower.push_back(v[0]);
	
	for(int i = 1; i < n; i++) {
		// upper_bound
		while(Upper.size() >= 2 && angle(Upper[Upper.size()-2],Upper[Upper.size()-1])  < angle(Upper[Upper.size()-1],v[i]) ) {
			Upper.pop_back();
		}
		Upper.push_back(v[i]);
		// lower_bound
		while(Lower.size() >= 2 && angle(Lower[Lower.size()-2],Lower[Lower.size()-1])  > angle(Lower[Lower.size()-1],v[i]) ) {
			Lower.pop_back();
		}
		Lower.push_back(v[i]);
	}
	cout << Lower.size() + Upper.size() - 2 << '\n';
	cout << setprecision(12) << fixed;
	for(auto &it : Lower)
		cout << it.x << ' ' << it.y << '\n';
	for(int i = Upper.size()-2; i >= 1; i--)
		cout << Upper[i].x << ' ' << Upper[i].y << '\n';
	
	
	return 0;
}