Cod sursa(job #1135933)

Utilizator vladrochianVlad Rochian vladrochian Data 8 martie 2014 16:25:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct point
{
	double x,y;
}p[120000];
int n,s[120000],si;
double area(point p1,point p2,point p3)
{
	return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}
bool cmp(point p1,point p2)
{
	return area(*p,p1,p2)>0;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main()
{
	int i;
	fin>>n;
	for(i=0;i<n;++i)
	{
		fin>>p[i].x>>p[i].y;
		if(p[i].x<p[0].x)
			swap(p[0],p[i]);
	}
	sort(p+1,p+n,cmp);
	for(i=1;i<n;++i)
	{
		while(si)
			if(area(p[s[si-1]],p[s[si]],p[i])>0)
				break;
			else
				--si;
		s[++si]=i;
	}
	fout<<++si<<"\n"<<setprecision(12)<<fixed;
	for(i=0;i<si;++i)
		fout<<p[s[i]].x<<" "<<p[s[i]].y<<"\n";
	return 0;
}