Cod sursa(job #2158309)

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


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

bool susjos(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];
point *prima, *ultima;

int stiva[120001], h=-1;

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, susjos);

	prima = &points[0];
	ultima = &points[n-1];

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

	for(i=2; i<n; i++) {
		relpos k = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
		if(k == LEFT)
			stiva[++h] = i;
		if(k == RIGHT) {
			while(k == RIGHT && --h > 1) {
				k = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
			}
			stiva[++h] = i;
		}
	}

	for(i=n-2; i>0; i--) {
		relpos k = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
		if(k == LEFT)
			stiva[++h] = i;
		if(k == RIGHT) {
			while(k == RIGHT && --h > 1) {
				k = unde(points[stiva[h-1]], points[stiva[h]], points[i]);
			}
			stiva[++h] = 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;
}