Cod sursa(job #1047938)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 4 decembrie 2013 23:54:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

struct punct{
	double x, y;
};

punct V[12000];
punct stiva[12000];
int best = 1;
int n = 0;

double prod(punct a, punct b, punct c){
	return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}

int compar(const punct a, const punct b){
	return prod(V[0], a, b)<0;
}

void sort(){
	best = 0;
	for (int i = 1; i < n; i++){
		if (V[best].x > V[i].x){
			best = i;
		}
		else{
			if (V[best].x == V[i].x && V[best].y>V[i].y){
				best = i;
			}
		}
	}
	punct aux = V[best];
	V[best] = V[0];
	V[0] = aux;
	sort(V + 1, V + n, compar);
}
int top;
void rezolva(){
	top = -1;
	stiva[++top] = V[0];
	stiva[++top] = V[1];
	for (int i = 2; i < n; i++){
		while (top>=2 && prod(stiva[top-1], stiva[top], V[i]) > 0){
			top--;
		}
		stiva[++top] = V[i];
	}
}

int main(){
	ifstream f("infasuratoare.in");
	ofstream cout("infasuratoare.out");
	f >> n;
	for (int i = 0; i < n; i++){
		punct p;
		f >> p.x;
		f >> p.y;
		V[i] = p;
	}
	sort();
	rezolva();
	cout << fixed;
	cout << top+1 << '\n';
	while (top>=0){
		cout << stiva[top].x<<" "<<stiva[top].y << '\n';
		top--;
	}
}