Cod sursa(job #717729)

Utilizator andreifirstCioara Andrei Ioan andreifirst Data 20 martie 2012 10:28:30
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

ifstream f("infasuratoare.in"); ofstream g("infasuratoare.out");

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

punct v[120005], stv[120005];
double x, y;
int i, j, n, b, mi;

inline bool comp (punct fx, punct fy){ return fx.p<fy.p; }

inline bool intoarcere (double x1, double y1, double x2, double y2, double x3, double y3){
	double rz;
	rz=x1*y2+x3*y1+x2*y3-x3*y2-x2*y1-x1*y3;	
	if (rz>0.0) return 1; else return 0;
}

int main(){
	
	//citirea si cautarea celui mai din stanga-jos punct
	y=1000000001.0; x=10000000001.0;
	f>>n;
	for (i=1; i<=n; i++){
		f>>v[i].x>>v[i].y;
		if (v[i].x<x || (v[i].x==x && v[i].y<y)){
			mi=i; y=v[i].y; x=v[i].x;
		}
	}
	
	//calculare unghiurilor polare
	for (i=1; i<=n; i++) {
		if (i!=mi) {
			if (v[i].x==x) v[i].p=1000000001.0;
			else if (v[i].y==y) v[i].p=0.0;
			else v[i].p=(v[i].y-y)/(v[i].x-x);
		}
	}
	
	//sortarea dupa unghiul polar
	sort (v+1, v+n+1, comp);
	
	//inserarea primelor doua elemente in stiva
	stv[1].x=v[mi].x; stv[1].y=v[mi].y; 
	stv[2].x=v[1].x; stv[2].y=v[1].y; 
	b=2;
	
	//rezolvarea stivei
	for (i=3; i<=n; i++) if (i!=mi){
		b++; stv[b].x=v[i].x; stv[b].y=v[i].y;
		
		while (b>2 && intoarcere (stv[b-2].x, stv[b-2].y, stv[b-1].x, stv[b-1].y, stv[b].x, stv[b].y)==0){
			b--; stv[b].x=v[i].x; stv[b].y=v[i].y;
		}
	}
	
	g<<b<<"\n";
	g<<fixed<<setprecision (12);
	for (i=1; i<=b; i++) g<<stv[i].x<<" "<<stv[i].y<<"\n";
			
		

	
		
}