Cod sursa(job #2014999)

Utilizator mihai.alphamihai craciun mihai.alpha Data 24 august 2017 20:00:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <cstdio>
#include <algorithm>

FILE *fin, *fout;

#define MAXN 120000

struct at {
	double x;
	double y;
};

int N;
at v[MAXN + 1];
int sti[MAXN + 1];
bool viz[MAXN + 1];
int i1, i0;
int d1, d0;

const double inf = 0.000000001;

bool cmp(at a, at b) {
	if (a.x == b.x) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

inline double ver(at i, at st, at dr) {
	return (st.x - i.x) * (dr.y - i.y) - (st.y - i.y) * (dr.x - i.x);
}

int main() {
	fin = fopen("infasuratoare.in", "r");
	fout = fopen("infasuratoare.out", "w");
	fscanf(fin, "%d", &N);
	for (int i = 1; i <= N; i++) {
		fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
	}
	std::sort(v + 1, v + N + 1, cmp);
	int stid = 2;
	sti[1] = 1;
	sti[2] = 2;
	for (int i = 1; i <= N; i++) {
		if (viz[i])
			continue;
		while (stid >= 2 && ver(v[sti[stid - 1]], v[sti[stid]], v[i]) < inf)
			viz[sti[stid--]] = 0;
		sti[++stid] = i;
		viz[i] = 1;
	}
	for (int i = N - 1; i > 0; i--) {
		if (viz[i])
			continue;
		while (stid >= 2 && ver(v[sti[stid - 1]], v[sti[stid]], v[i]) < inf)
			viz[sti[stid--]] = 0;
		sti[++stid] = i;
		viz[i] = 1;
	}
	fprintf(fout, "%d\n", stid - 1);
	for (int i = 1; i <= stid - 1; i++)
		fprintf(fout, "%lf %lf\n", v[sti[i]].x, v[sti[i]].y);
	fclose(fin);
	fclose(fout);
	return 0;
}