Cod sursa(job #1408236)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 29 martie 2015 22:14:42
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120000
using namespace std;
FILE *fin, *fout;
int n, p, sum;
bool f;
struct punct
{
	double x;
	double y;
	double f1;
	double f2;
} v[NMAX], stiva[NMAX];
bool comp(punct a, punct b)
{
	return (a.f1 * b.f2 < b.f1 * a.f2);
}
int main()
{
	fin = freopen("infasuratoare.in", "r", stdin);
	fout = freopen("infasuratoare.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 0; i< n; i++)
	{
		scanf("%lf %lf", &v[i].x, &v[i].y);
		if(i == 0) continue;
		if(v[i].x < v[p].x) p = i;
		else if(v[i].x == v[p].x)
		{
			if(v[i].y < v[p].y) p = i;
		}
	}
	swap(v[p], v[0]);
	for(int i = 1; i< n; i++)
	{
		v[i].f1 = v[i].y - v[0].y;
		v[i].f2 = v[i].x - v[0].x;
	}
	sort(v+1, v+n, comp);
	stiva[0].x = v[0].x;
	stiva[0].y = v[0].y;
	stiva[1].x = v[1].x;
	stiva[1].y = v[1].y;
	p = 1;
	for(int i = 2; i< n; i++)
	{
		f = 0;
		while(p>=1 && f == 0)
		{
			sum = stiva[p-1].x*stiva[p].y + stiva[p].x*v[i].y + v[i].x*stiva[p-1].y - v[i].x*stiva[p].y - stiva[p].x*stiva[p-1].y - stiva[p-1].x*v[i].y;
			if(sum > 0)
			{
				p++;
				stiva[p].x = v[i].x;
				stiva[p].y = v[i].y;
				f = 1;
			}
			if(sum < 0)
			{
				p--;
			}
		}
	}
	printf("%d\n", p+1);
	for(int i = 0; i<= p; i++) printf("%lf %lf\n", stiva[i].x, stiva[i].y);
	fclose(fin);
	fclose(fout);
	return 0;
}