Cod sursa(job #933517)

Utilizator raulstoinStoin Raul raulstoin Data 30 martie 2013 01:00:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<algorithm>
#include<utility>
#define NMAX 120005
#define x second
#define y first
#define TYPE pair <double,double>
using namespace std;
int n,l;
TYPE v[NMAX],s[NMAX];
void read()
{
	ifstream fin("infasuratoare.in");
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>v[i].x>>v[i].y;
	fin.close();
}
void print()
{
	ofstream fout("infasuratoare.out");
	fout<<l<<'\n';
	for(int i=l;i;i--)
		fout<<fixed<<s[i].x<<' '<<s[i].y<<'\n';
	fout.close();
}
inline double area(TYPE a,TYPE b,TYPE c)
{
	return 	a.x * b.y + b.x * c.y + c.x * a.y -
			b.x * a.y - c.x * b.y - a.x * c.y;
}
inline bool cmp(TYPE a,TYPE b)
{
	return (area(v[1],a,b)<0);
}
void solve()
{
	for(int i=2;i<=n;i++)
		if(v[i]<v[1])
			swap(v[i],v[1]);
	sort(v+2,v+n+1,cmp);
	s[++l]=v[1];
	s[++l]=v[2];
	for(int i=3;i<=n;i++)
	{
		while(l>1 && area(s[l-1],s[l],v[i])>0)
			l--;
		s[++l]=v[i];
	}
}
int main()
{
	read();
	solve();
	print();
	return 0;
}