Cod sursa(job #402806)

Utilizator vasilemureVasile Mure vasilemure Data 24 februarie 2010 10:22:49
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <algorithm>

#define Nmax 120005
#define inf 1<<30

using namespace std;

int n, i, j, niv, pctmin;
int stiva[Nmax];
double xmin, ymin = inf, A;


struct infasuratoare{
	double x, y;
} V[Nmax], aux;


int comp(infasuratoare a, infasuratoare b){
	return a.x * b.y >= b.x * a.y;
}

int convex (infasuratoare a, infasuratoare b, infasuratoare c){
	
	A = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
	if (A > 0) 
		return 1;
	return 0;
	
}

int main (){
	
	FILE * f = fopen ("infasuratoare.in", "r");
	FILE * g = fopen ("infasuratoare.out", "w");
	
	fscanf (f, "%d", &n);
	for (i = 1 ; i <= n ; i++){
		fscanf(f, "%lf %lf", &V[i].x, &V[i].y);
		if (ymin > V[i].y){
			xmin = V[i].x;
			ymin = V[i].y;
			pctmin = i;	
		}
	}
	
	for (i = 1 ; i <= n ; i++){
		V[i].x -= xmin;
		V[i].y -= ymin;
	}
	
	aux = V[1];
	V[1] = V[pctmin];
	V[pctmin] = aux;

	sort (V+2, V+n+1, comp); 
	
	
	stiva[1] = 1;
	stiva[2] = 2;
	niv = 2;
	
	for (i = 3 ; i <= n ; i++){
		while ( niv >= 3 && !convex(V[stiva[niv-1]], V[stiva[niv]], V[i]) )
			niv --;
		
		stiva[++niv] = i;
	}
	
	fprintf (g, "%d\n", niv);
	for (i = 1 ; i <= niv ; i++) 
		fprintf (g, "%lf %lf\n", V[stiva[i]].x + xmin, V[stiva[i]].y + ymin);	
	
	fclose(f);
	fclose(g);
	return 0; 
}