Cod sursa(job #2921713)

Utilizator alt_contStefan alt_cont Data 1 septembrie 2022 15:18:35
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <iomanip>
#define epsilon 1e-12

using namespace std;

typedef pair<double,double> Point;
Point points[150000];

Point operator-(Point a, Point b){
	return Point(a.first - b.first, a.second - b.second);
}

double angle(Point a){
	return atan2(a.first, a.second);
}

bool concave(Point a, Point b, Point c){
	double theta1 = angle(a - b);
	double theta2 = angle(c - b);
	double diff = theta2 - theta1;
	if(diff > M_PI + epsilon)
		return false;
	else if(diff < -M_PI - epsilon)
		return true;
	else if(diff > epsilon)
		return true;
	else 
		return false;
}

struct {
    bool operator()(Point a, Point b) const { return angle(a - points[0]) < angle(b - points[0]); }
} angularLess;



int main(){
	ifstream fin("infasuratoare.in");
	ofstream fout("infasuratoare.out");
	int n;
	double x, y;
	fin >> n;
	for(int i = 0; i < n; ++i){
		fin >> points[i].first >> points[i].second;
	}

	// find leftmost point
	for(int i = 1; i < n; ++i){
		if(points[i].first < points[0].first)
			swap(points[0], points[i]);
	}

	// angular sort
	sort(points + 1, points + n, angularLess);

	stack<Point> stk;
	stk.push(points[0]);
	stk.push(points[1]);

	// construct hull
	for(int i = 2; i < n; ++i){
		while(true){
			Point last = stk.top();
			stk.pop();
			Point second_last = stk.top();

			if(!concave(second_last, last, points[i])){
				stk.push(last);
				stk.push(points[i]);
				break;
			}
		}
	}


	fout << stk.size() << "\n";
	while(!stk.empty()){
		fout << fixed << setprecision(6) << stk.top().first << " " << stk.top().second << "\n";
		stk.pop();
	}


}