Cod sursa(job #664278)

Utilizator avram_florinavram florin constantin avram_florin Data 19 ianuarie 2012 21:18:57
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<fstream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int MaxN = 120001;

const char InFile[] = "infasuratoare.in";
const char OutFile[] = "infasuratoare.out";

int n,vfs,st[MaxN << 1];

struct punct{
	double x,y;
	} P[MaxN];
vector<punct> V;

bool cmp(punct a , punct b)
{
	if( a.x != b.x )
		return a.x < b.x;
	return a.y < b.y;
}

double sarrus( punct a , punct b , punct c )
{
	return  a.x*b.y + b.x*c.y + c.x*a.y - b.y*c.x - b.x*a.y - a.x*c.y;
}

int main()
{
	ifstream fin ( InFile );
	ofstream fout ( OutFile );
	fin >> n;
	int i;
	for( i = 1 ; i <= n ; i++ )
		fin >> P[i].x >> P[i].y;
	fin.close();
	sort( P+1 , P+n+1 , cmp );
	vfs = 1;
	st[vfs] = 1;
	st[++vfs] = 2;
	for( i = 3 ; i <= n ; i++ )
		{
			while( vfs > 1 && sarrus(P[st[vfs-1]],P[st[vfs]],P[i]) < 0 )
				--vfs;
			st[++vfs] = i;
		}
	for( i = 1 ; i <= vfs ; ++i )
		V.push_back(P[st[i]]);
	vfs = 1;
	st[vfs] = n;
	st[++vfs] = n-1;
	for( i = n-2 ; i ; --i )
		{
			while( vfs > 1 && sarrus(P[st[vfs-1]],P[st[vfs]],P[i]) < 0 )
				--vfs;
			st[++vfs] = i;
		}
	for( i = 2 ; i < vfs ; ++i )
		V.push_back(P[st[i]]);
	vector<punct>::iterator it,iend;
	iend = V.end();
	fout << V.size() << '\n';
	for( it = V.begin() ; it != iend ; ++it )
		fout << it -> x << ' ' << it -> y << '\n';
	fout.close();
	return 0;
}