Cod sursa(job #2195542)

Utilizator ZenusTudor Costin Razvan Zenus Data 16 aprilie 2018 18:38:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

#define point pair < double, double >
const int Nmax = 120000;

point a[Nmax];
int stk[Nmax]; 
int n, m;

void readData() {
	freopen("infasuratoare.in" , "r" , stdin);
	freopen("infasuratoare.out" , "w" , stdout);

	scanf("%d", &n);

	srand(time(0));
}

double getUnit() {
	int Y = 1000000000;
	int X = (1LL * rand() * rand()) % (Y + 1);
	return 1.0 * X / Y;
}

double cross_product(point A, point B, point C) {
	return (A.first - C.first) * (B.second - C.second) - (B.first - C.first) * (A.second - C.second);
}

bool compare(point A, point B) {
	return cross_product(a[0] , A , B) > 0;
}

void readPoints() {
	for (int i = 0 ; i < n ; ++i)
		scanf("%lf%lf", &a[i].first, &a[i].second);
}

void generate() {
	for (int i = 0 ; i < n; ++i) {
		a[i].first = getUnit();
		a[i].second = getUnit();
	}
}

void graham() {

	int j = 0;
	for (int i = 0 ; i < n ; ++i) {
			if (a[i] < a[j])
				j = i;
	}

	swap(a[0], a[j]);
	sort(a + 1, a + n, compare);

	stk[++m] = 0;
	stk[++m] = 1;

	for (int i = 2 ; i < n ; ++i) {
		while (m >= 2 && cross_product(a[stk[m]], a[stk[m-1]], a[i]) >= 0)
			m--;

		stk[++m] = i;
	}

	printf("%d\n", m);
	for (int i = 1 ; i <= m ; ++i) {
		printf("%.7lf %.7lf\n", a[stk[i]].first, a[stk[i]].second);
	}
}

int main() {
	
	readData();
	//generate();
	readPoints();
	graham();

	return 0;
}