Cod sursa(job #2985652)

Utilizator ViAlexVisan Alexandru ViAlex Data 26 februarie 2023 19:07:35
Problema Infasuratoare convexa Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
#include<iomanip>
using namespace std;

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

struct point{
	double x,y;
};

// Used to find the first node.
bool compare(const point&a, const point&b){
	return a.x<b.x || (a.x==b.x && a.y<b.y);
}

// Returns a number value between 0 and max.
int random(int max){
	return rand()%max;
}

/* 1    1   1
 * a.x b.x c.x
 * a.y b.y c.y
 */
double determinant(const point&a, const point&b, const point&c){
	return b.x*c.y + a.x*b.y + a.y*c.x - b.x*a.y - c.x*b.y - c.y*a.x;
}


int n;
vector<point> points;

void read(){
	in>>n;
	points.resize(n);
	for(int i=0;i<n;i++){
		in>>points[i].x>>points[i].y;
	}
}

void solve(){
	int first = 0;
	for(int i=1;i<n;i++){
		if(compare(points[i],points[first])){
			first = i; 
		}
	}
	vector<point> hull;
	bool stop = false;
	int current = first;

	while(!stop){
		hull.push_back(points[current]);

		int pivot;
		do{
			pivot = random(n);
		}
		while(pivot==current);
		
		for(int i=0;i<n;i++){
			if(determinant(points[current],points[pivot],points[i])<0.0){
				pivot = i;	
			}
		}
		if(pivot == first){
			stop = true;
		}
		current = pivot;
	}
	out<<hull.size()<<'\n';
	for(point p:hull){
		out<<fixed<<setprecision(10)<<p.x<<" "<<p.y<<'\n';
	}
}


int main(){
	read();
	solve();

	return 0;
}