Cod sursa(job #715197)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 16 martie 2012 20:26:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 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;
}a[NMAX];
int n, vz[NMAX], ord[NMAX+NMAX], aux, S[NMAX];

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

bool cmp(punct A, punct B)
{
	if (A.x<B.x || (A.x==B.x && A.y<B.y)) return 1;
	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 m=2, i, j;
	double P;
	punct aux;
	for (i=1, j=2*n; i<=n; ++i, --j)
		ord[i]=ord[j]=i;
	S[1]=1; S[2]=2; vz[2]=1;
	for (i=3; i<=2*n; ++i)
		if (!vz[ord[i]])
		{
			aux=a[ord[i]];
			P=plan(a[S[m-1]], a[S[m]], aux);
			while (P>=0 && m>1)
			{
				vz[S[m]]=0; S[m--]=0;
				P=plan(a[S[m-1]], a[S[m]], aux);
			}
			S[++m]=ord[i]; vz[ord[i]]=1;
		}
	g<<m-1<<"\n";
	for (i=m-1; i>0; --i) g<<fixed<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";
}

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