Cod sursa(job #1807359)

Utilizator bullseYeIacob Sergiu bullseYe Data 16 noiembrie 2016 13:55:05
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120010
using namespace std;

struct pct {
	double x, y;
};

pct P[NMAX], S[NMAX];
int vfS, n;

void citire();
void Graham();
inline bool cmp(const pct&, const pct&);
inline double crossProduct(const pct&, const pct&, const pct&);
void afisare();

int main() {
	citire();
	Graham();
	afisare();
	return 0;
}

void citire() {
	FILE*fin = fopen("infasuratoare.in", "r");
	fscanf(fin, "%d", &n);

	unsigned int i;
	for (i = 1; i <= n; ++i)
		fscanf(fin, "%lf %lf", &P[i].x, &P[i].y);
	fclose(fin);
	return;
}

void Graham() {
	unsigned int bottomLeftPoint = 1;

	for (i = 2; i <= n; ++i)
		if (P[i].y<P[bottomLeftPoint].y || (P[i].y == P[bottomLeftPoint].y && P[i].x<P[bottomLeftPoint].x)) {
			bottomLeftPoint = i;
		}

	swap (P[bottomLeftPoint], P[1]);
	sort (P + 2, P + n + 1, cmp);

	S[1] = P[1]; S[2] = P[2]; vfS = 2;

    unsigned int i;
	for (i = 3; i <= n; ++i) {
		while (vfS>1 && crossProduct(S[vfS - 1], S[vfS], P[i]) <= 0)
			--vfS;
		S[++vfS] = P[i];
	}
	return;
}

inline double crossProduct(const pct &a, const pct &b, const pct &c) {
	return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}

inline bool cmp(const pct &a, const pct &b) {
	return crossProduct(P[1], a, b)>0;
}

void afisare() {
	FILE*fout = fopen("infasuratoare.out", "w");
	fprintf(fout, "%d\n", vfS);

	unsigned int i;
	for (i = 1; i <= vfS; ++i)
		fprintf(fout, "%f %f\n", S[i].x, S[i].y);
	fclose(fout);
	return;
}