Cod sursa(job #573534)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 6 aprilie 2011 12:50:40
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>

using namespace std;

const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
const int  nmax    = 125000;

struct point 
{
	double	x, y;
	double panta;
}p[nmax];

int n, i, vf;
double mxx, mxy;
int maxpoint;
int st[nmax];

double calc(int i)
{
	return (p[i].y - p[1].y) / (p[i].x - p[1].x);
}

struct cmp
{
	bool operator()(const point &a, const point &b)const
	{
		if(a.panta < b.panta)
			return 1;
		if(a.panta == b.panta)
			if(a.x < b.x)
				return 1;
		return 0;
	}
};

double ccw(int p1, int p2, int p3)
{
	return (p[p2].x - p[p1].x) * (p[p3].y - p[p1].y) - (p[p2].y - p[p1].x) * (p[p3].x - p[p1].x);
}

int main()
{	
	freopen(iname, "r", stdin);
	freopen(oname, "w", stdout);
	mxx = 2920910;
	mxy = 2902902;
	scanf("%d", &n);
	for(i = 1; i <= n; i ++)
	{
		scanf("%lf %lf", &p[i].x, &p[i].y);
		if(p[i].x < mxx)
		{
			mxx = p[i].x;
			maxpoint = i;
		}
		if(p[i].x == mxx)
			if(p[i].y < mxy)
			{
				mxy = p[i].y;
				maxpoint = i;
			}
	}
	
	swap(p[1], p[maxpoint]);
	for(i = 2; i <= n; i ++)
		p[i].panta = calc(i);
	
	
	sort(p + 2, p + n + 1, cmp());
	st[1] = 1, st[2] = 2;
	vf = 2;
	for(i = 3; i <= n; i ++)
	{
		while(vf > 2 && ccw(st[vf - 1], st[vf], i) < 0) //atentie
			--vf;
		st[++vf] = i;
	}
	
	printf("%d\n", vf);
	for(i = 1; i <= vf; i ++)
		printf("%lf %lf\n", p[st[i]].x, p[st[i]].y);
	return 0;
}