Cod sursa(job #402147)

Utilizator Addy.Adrian Draghici Addy. Data 23 februarie 2010 15:32:40
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 120500
#define INF 1LL << 60

using namespace std;

struct punct {
	double x, y, ctg;
} ;

punct v[Nmax];
int S[Nmax], n, N, i, pmin;
double xmin, ymin;

double cmp(punct a, punct b) {
	return a.ctg > b.ctg;
}

int convex(int P1, int P2, int P3) {
	long double A, X1, Y1, X2, Y2, X3, Y3;
	
	X1 = v[P1].x, Y1 = v[P1].y, X2 = v[P2].x, Y2 = v[P2].y, X3 = v[P3].x, Y3 = v[P3].y;
	A = (X3 - X2) * (Y1 - Y2) - (X1 - X2) * (Y3 - Y2);
	
	if (A > 0)
		return 1;
	return 0;
}

void infasuratoare() {
	int i; punct aux;
	
	aux = v[1], v[1] = v[pmin], v[pmin] = aux;
	
	for (i = 2; i <= n; i++) {
		v[i].x -= v[1].x, v[i].y -= v[1].y;
		v[i].ctg = v[i].x / v[i].y;
	}
	
	sort(v + 2, v + 1 + n, cmp);
	
	N = 2, S[1] = 1, S[2] = 2;
	for (i = 3; i <= n; i++) {
		while (N > 2 && !convex(S[N-1], S[N], i))
			N--;
		
		S[++N] = i;
	}
}

void afisare() {
	int i;
	
	FILE *g = fopen("infasuratoare.out", "w");
	
	fprintf(g, "%d\n%lf %lf\n", N, v[1].x, v[1].y);
	
	for (i = 2; i <= N; i++)
		fprintf(g, "%lf %lf\n", v[S[i]].x + xmin, v[S[i]].y + ymin);
	
	fclose(g);
}

void citire() {
	int i;
	
	FILE *f = fopen("infasuratoare.in", "r");
	
	fscanf(f, "%d", &n);
	
	ymin = INF;
	for (i = 1; i <= n; i++) {
		fscanf(f, "%lf %lf", &v[i].x, &v[i].y);
		if (v[i].y < ymin)
			xmin = v[i].x, ymin = v[i].y, pmin = i;
	}
	
	fclose(f);
}

int main() {
	
	citire();
	
	infasuratoare();
	
	afisare();
	
	return 0;
}