Cod sursa(job #616227)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 11 octombrie 2011 23:03:28
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N=120001;

struct punct{
	double x,y;
}x[N],y[N],z[N];
	
bool comp(punct a,punct b){
	return a.x<b.x;
}

int n,nr1,nr2;

int main(){
	int i;
	in>>n;
	for(i=1;i<=n;i++){
		in>>x[i].x>>x[i].y;
	}
	sort(&x[1],&x[n+1],comp);
	y[++nr1]=x[1];
	for(i=2;i<=n;i++){
		while(nr1>1 && (x[i].y - y[nr1].y) * (x[i].x - y[nr1-1].x) <= (x[i].x - y[nr1].x) * (x[i].y - y[nr1-1].y))
			--nr1;
		y[++nr1]=x[i];
	}
	z[++nr2]=x[1];
	for(i=2;i<=n;++i){		
		while(nr2>1 && (x[i].y - z[nr2].y) * (x[i].x - z[nr2-1].x) >= (x[i].x - z[nr2].x) * (x[i].y - z[nr2-1].y))
			--nr2;
		z[++nr2]=x[i];
	}
	out<<nr1+nr2-2<<"\n";
	for(i=1;i<=nr1;++i)
		out<<y[i].x<<" "<<y[i].y<<"\n";
	for(i=nr2-1;i>1;--i)
		out<<z[i].x<<" "<<z[i].y<<"\n";
	return 0;
}