Cod sursa(job #914474)

Utilizator Kira96Denis Mita Kira96 Data 14 martie 2013 10:16:43
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<fstream>
#include<algorithm>
#define DIM 120100
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,s[DIM],k;
bool viz[DIM];
struct el
{
	float x,y;
}v[DIM];
float cm(el A,el B)
{
	if(A.y!=B.y)
	return A.y<B.y;
	return A.x<B.x;
}
float det(int i,int j,int k)
{
	float D;
	D=v[i].x*v[j].y+v[j].x*v[k].y+v[i].y*v[k].x-v[i].y*v[j].x-v[j].y*v[k].x-v[i].x*v[k].y;
	return D;
}
int main ()
{
	f>>n;
	for(i=1;i<=n;++i)
	f>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,cm);
	viz[2]=1;
	s[1]=1; s[2]=2;
	k=2;
	for(i=3;i<=n;++i)
	{
		if(det(s[k],s[k-1],i)<0)
		{
		s[++k]=i; viz[i]=1; 
		}
		else
		{
			while(det(s[k],s[k-1],i)>=0&&k>1)
			{ viz[s[k]]=0; s[k]=0; k--; }
			s[++k]=i;
			viz[i]=1;
		}
	}
	for(i=n-1;i>1;--i)
	{
		if(!viz[i])
		if(det(s[k],s[k-1],i)<0)
		{
			s[++k]=i; viz[i]=1;
		}
		else
		{
			while(det(s[k],s[k-1],i)>=0&&k>1)
			{ viz[s[k]]=0; s[k]=0; k--; }
			s[++k]=i;
			viz[i]=1;
		}
	}
	g<<k<<"\n";
	for(i=1;i<=k;++i)
		g<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
	return 0;
}