Cod sursa(job #714433)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 15 martie 2012 19:09:05
Problema Infasuratoare convexa Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define NMAX 120010
#define EPS 0.00000000001

using namespace std;

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

struct punct
{
	double x, y;
	int o;
}a[NMAX];
int n, st1[NMAX], st2[NMAX];

void Citeste()
{
	int i;
	f>>n;
	for (i=1; i<=n; ++i) f>>a[i].x>>a[i].y;
}

inline bool cmp(punct A, punct B)
{
	if (fabs(A.x-B.x)<EPS)
		if (A.y-B.y<EPS) return 1;
		else return 0;
	else if (A.x-B.x<EPS) return 1;
			else return 0;
}

double plan(punct A, punct B, punct C)
{
	return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}

void Solve()
{
	int i, m=3, x, y, z;
	double P;
	
	st1[1]=1; st1[2]=2; st1[3]=3;
	
	for (i=4; i<=n; ++i)
	{
		if (plan(a[st1[m]], a[st1[m-1]], a[i])>EPS) st1[++m]=i;
		else
		{
			while (plan(a[st1[m]], a[st1[m-1]], a[i])<EPS || fabs(plan(a[st1[m]], a[st1[m-1]], a[i]))==EPS) --m;
			st1[++m]=i;
		}
	}
	
	for (i=1; i<=m; ++i) a[st1[i]].o=i;
	x=m;
	//x=st[n]; y=st[n-1]; z=st[n-2]; m=3;
	st2[1]=n; st2[2]=n-1; st2[3]=n-2; m=3;
	
	for (i=n-3; i>0; --i)
		if (a[i].o<2)
		{
			P=plan(a[st2[m]], a[st2[m-1]], a[i]);
			if (P>EPS) st2[++m]=i;
			else
			{
				while (plan(a[st2[m]], a[st2[m-1]], a[i])<EPS || fabs(plan(a[st2[m]], a[st2[m-1]], a[i]))==EPS) --m;
				st2[++m]=i;
			}
		}
	g<<m+x-2<<"\n";
	for (i=x; i>0; --i) g<<fixed<<a[st1[i]].x<<" "<<a[st1[i]].y<<"\n";
	for (i=m-1; i>1; --i) g<<fixed<<a[st2[i]].x<<" "<<a[st2[i]].y<<"\n";
	
}

int main()
{
	Citeste();
	sort(a+1, a+n+1, cmp);
	Solve();
	f.close();
	g.close();
	return 0;
}