Cod sursa(job #1807369)

Utilizator bullseYeIacob Sergiu bullseYe Data 16 noiembrie 2016 13:58:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120010

using namespace std;

struct pct {
	double x, y;
};

pct points[NMAX], stack[NMAX];
unsigned 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", &points[i].x, &points[i].y);
	fclose(fin);
	return;
}

void Graham() {
	unsigned int bottomLeftPoint = 1, i;

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

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

	stack[1] = points[1]; stack[2] = points[2]; vfS = 2;

	for (i = 3; i <= n; ++i) {
		while (vfS>1 && crossProduct(stack[vfS - 1], stack[vfS], points[i]) <= 0)
			--vfS;
		stack[++vfS] = points[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(points[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", stack[i].x, stack[i].y);
	fclose(fout);
	return;
}