Cod sursa(job #2014932)

Utilizator mihai.alphamihai craciun mihai.alpha Data 24 august 2017 17:29:47
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.82 kb
#include <cstdio>
#include <algorithm>

FILE *fin, *fout;

#define MAXN 120000

struct at {
	double x;
	double y;
};

int N;
at v[MAXN + 1];
at p1[MAXN + 1], p0[MAXN + 1];
int inf1[MAXN + 1], inf0[MAXN + 1];
double Cos1[MAXN + 1], Cos0[MAXN + 1];
int i1, i0;
int d1, d0;

const double inf = 0.000001;

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

inline bool ver(int i, int st, int dr) {
	if (abs(v[st].x - v[dr].x) < inf) {
		if (v[i].x > v[st].x)
			return 0;
		else
			return 1;
	}
	else if (abs(v[st].y - v[dr].y) < inf) {
		if (v[i].y > v[st].y)
			return 1;
		else
			return 0;
	}
	else {
		double A = (v[st].x - v[dr].x) / (v[st].y - v[dr].y);
		double B = A * v[st].x - v[st].y;
		double Y;
		Y = A * v[i].x + B;
		if ((Y - v[i].y) < 0.0)
			return 1;
		else
			return 0;
	}
}

int main() {
	fin = fopen("infasuratoare.in", "r");
	fout = fopen("infasuratoare.out", "w");
	fscanf(fin, "%d", &N);
	int st, dr;
	st = dr = 1;
	fscanf(fin, "%lf%lf", &v[1].x, &v[1].y);
	for (int i = 2; i <= N; i++) {
		fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
		if (v[i].x < v[st].x) {
			st = i;
		}
		if (v[i].x > v[dr].x) {
			dr = i;
		}
	}
	for (int i = 1; i <= N; i++) {
		if (i != st && i != dr) {
			if (ver(i, st, dr) == 1)  {
				p1[++i1].x = v[i].x;
				p1[i1].y = v[i].y;
			}
			else {
				p0[++i0].x = v[i].x;
				p0[i0].y = v[i].y;
			}
		}
	}
	std::sort(p1 + 1, p1 + i1 + 1, cmp);
	std::sort(p0 + 1, p0 + i0 + 1, cmp);
	for (int i = 1; i <= i0; i++) {
		double l1, l2, l3;
		l1 = (v[dr].x - v[st].x) * (v[dr].x - v[st].x) +
			(v[dr].y - v[st].y) * (v[dr].y - v[st].y);
		l3 = (v[dr].x - p0[i].x) * (v[dr].x - p0[i].x) +
			(v[dr].y - p0[i].y) * (v[dr].y - p0[i].y);
		l2 = (v[st].x - p0[i].x) * (v[st].x - p0[i].x) +
			(v[dr].y - p0[i].y) * (v[dr].y - p0[i].y);
		double Cos;
		Cos = (-l3 + l1 + l2) / sqrt(4.0 * l1 * l2);
		Cos0[i] = Cos;
		while (d0 > 0 && Cos0[inf0[d0]] > Cos)
			d0--;
		inf0[++d0] = i;
	}
	for (int i = 1; i <= i1; i++) {
		double l1, l2, l3;
		l1 = (v[dr].x - v[st].x) * (v[dr].x - v[st].x) +
			(v[dr].y - v[st].y) * (v[dr].y - v[st].y);
		l3 = (v[dr].x - p1[i].x) * (v[dr].x - p1[i].x) +
			(v[dr].y - p1[i].y) * (v[dr].y - p1[i].y);
		l2 = (v[st].x - p1[i].x) * (v[st].x - p1[i].x) +
			(v[dr].y - p1[i].y) * (v[dr].y - p1[i].y);
		double Cos;
		Cos = (-l3 + l1 + l2) / sqrt(4.0 * l1 * l2);
		Cos1[i] = Cos;
		while (d1 > 0 && Cos1[inf1[d1]] > Cos) {
			d1--;
		}
		inf1[++d1] = i;
	}
	fprintf(fout, "%d\n", d1 + d0 + 2);
	fprintf(fout, "%lf %lf\n", v[st].x, v[st].y);
	for (int i = 1; i <= d0; i++)
		fprintf(fout, "%lf %lf\n", p0[inf0[i]].x, p0[inf0[i]].y);
	fprintf(fout, "%lf %lf\n", v[dr].x, v[dr].y);
	for (int i = d1; i >= 1; i--)
		fprintf(fout, "%lf %lf\n", p1[inf1[i]].x, p1[inf1[i]].y);
	fclose(fin);
	fclose(fout);
	return 0;
}