Cod sursa(job #292212)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 30 martie 2009 21:24:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define semn(i1,i2,i3) (db) X[i1] * Y[i2] + X[i2] * Y[i3] + X[i3] * Y[i1] - Y[i1] * X[i2] - Y[i2] * X[i3] - Y[i3] * X[i1]
#define IN  "infasuratoare.in"
#define OUT "infasuratoare.out"
#define N_MAX 1<<17

int N,last,pi;
db X[N_MAX],Y[N_MAX];
int A[N_MAX],S[N_MAX];

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	
	scanf("%d\n",&N);
	
	FOR(i,1,N)
		scanf("%lf %lf\n",&X[i],&Y[i]);
}

II bool comp(int i,int j)
{
	return (X[i] - X[pi]) * (Y[j] - Y[pi]) < (X[j] - X[pi]) * (Y[i] - Y[pi]);
}

II void solve()
{
	X[0] = Y[0] = 1<<30;
	FOR(i,1,N)
		if(X[i] < X[pi] || (X[i] == X[pi] && Y[i] < Y[pi]) )
			pi = i;
	
	FOR(i,1,N)
		if(i != pi)
			A[++A[0]] = i;
	sort(A+1,A+A[0]+1,comp);
	
	S[++last] = pi;
	S[++last] = A[0];
	FOR(i,1,A[0])
	{
		for(;last >= 2 && semn(S[last-1],S[last],A[i]) > 0;--last);
		S[++last] = A[i];
	}

	printf("%d\n",last);
	for(int i=last;i>=1;--i)
		printf("%lf %lf\n",X[ S[i] ],Y[ S[i] ]);
 }

int main()
{
	scan();
	solve();
	return 0;
}