Cod sursa(job #2158314)

Utilizator dragomir_ioanDragomir Ioan dragomir_ioan Data 10 martie 2018 11:57:33
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <algorithm>
#include <cstdio>


typedef double field;
#define zero ((field)0)
typedef struct point {field x, y;} point;

bool susjosstangadreapta(point a, point b) {
	return (a.y == b.y) ? (a.x < b.x) : (a.y < b.y);
}

typedef enum relpos {LEFT = 1, RIGHT = -1, ON = 0} relpos;

relpos unde(point a, point b, point c) {
	field det = a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
	if(det < zero) return RIGHT;
	if(det > zero) return LEFT;
	return ON;
}

point points[120000];
int stiva[120001], h=-1;

inline void baga_punct(int i) {
	relpos in_care_semiplan = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
	if(in_care_semiplan == LEFT)
		stiva[++h] = i;
	if(in_care_semiplan == RIGHT) {
		while(in_care_semiplan == RIGHT && --h > 1)
			in_care_semiplan = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
		stiva[++h] = i;
	}
}

int main() {
	int n, i;

	FILE *fin = fopen("infasuratoare.in", "r");
	fscanf(fin, "%d", &n);
	for(i=0; i<n; i++)
		fscanf(fin, "%lf%lf", &points[i].x, &points[i].y);
	fclose(fin);

	std::sort(points, points+n, susjosstangadreapta);

	stiva[++h] = 0;
	stiva[++h] = 1;

	for(i=2; i <= n-1; i++) baga_punct(i);
	for(i=n-2; i >= 1; i--) baga_punct(i);

	FILE *fout = fopen("infasuratoare.out", "w");
	fprintf(fout, "%d\n", h+1);
	for(i=0; i<=h; i++) {
		fprintf(fout, "%.6lf %.6lf\n", points[stiva[i]].x, points[stiva[i]].y);
	}
	fclose(fout);

	return 0;
}