Cod sursa(job #1174874)

Utilizator sorin2kSorin Nutu sorin2k Data 24 aprilie 2014 00:53:09
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<fstream>
#include<cstdlib>
#include<iomanip>
using namespace std;

struct Punct {
	double x, y;
};

Punct v[120001], pmin;
int st[120002], imin;
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

void afla_min() {
	int i;
	pmin.x = v[0].x;
	pmin.y = v[0].y;
	imin = 0;
	for(i = 1; i < n; i++) {
		if(v[i].y < pmin.y) {
			pmin.x = v[i].x;
			pmin.y = v[i].y;
			imin = i;
		} else {
			if(v[i].y == pmin.y && v[i].x < pmin.x) {
				pmin.x = v[i].x;
				imin = i;
			}
		}
	}
}

// calculeaza valoarea pe axa Z a produsului vectorial dintre AB si BC
double cross(Punct a, Punct b, Punct c) {
	double det;
	det = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
	return det;
}

int compar(const void *a, const void *b) {
	Punct pa = *(Punct *)a;
	Punct pb = *(Punct *)b;
	return (cross(pmin, pa, pb) > 0) ? -1 : 1;
}

void infasuratoare() {
	int i;
	st[++st[0]] = 0;
	st[++st[0]] = 1;
	for(i = 2; i < n; i++) {
		st[++st[0]] = i;
		// cat timp am in stiva mai mult de 2 puncte si ultimele 3 formeaza un nod exterior, elimina-l pe cel din mijloc
		while(st[0] > 2 && cross(v[st[st[0]-2]], v[st[st[0]-1]], v[st[st[0]]]) < 0) {
			st[st[0]-1] = st[st[0]];
			st[0]--;
		}
	}
}

int main() {
	int i;
	Punct aux;
	fin >> n;
	for(i = 0; i < n; i++) {
		fin >> v[i].x >> v[i].y;
	}
	afla_min();
	// pune punctul minim pe prima pozitie
	aux = v[0];
	v[0] = v[imin];
	v[imin] = aux;
	// sorteaza restul de n-1 puncte dupa unghiul pe care il fac cu v[0]
	qsort(v+1, n-1, sizeof(Punct), compar);
	v[n++] = v[0];
	infasuratoare();
	fout << st[0]-1 << "\n";
	fout << setprecision(6);
	fout << fixed;
	for(i = 1; i < st[0]; i++) {
		fout << v[st[i]].x << " " << v[st[i]].y << "\n";
	}
	return 0;
}