Cod sursa(job #1408193)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 29 martie 2015 21:46:46
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <algorithm>
#define NMAX 120023
using namespace std;
FILE *fin, *fout;
int n, p, nr;
bool f;
struct punct
{
	double x;
	double y;
} v[NMAX], v2[NMAX], r;
bool comp(punct a, punct b)
{
	int ar = r.x*a.y + a.x*b.y + b.x*r.y - b.x*a.y - a.x*r.y - r.x*b.y;
	return (ar > 0);
}
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;
		}
	}
	for(int i = 0; i< n; i++)
	{
		if(i == p) continue;
		v2[nr].x = v[i].x;
		v2[nr].y = v[i].y;
		nr++;
	}
	r.x = v[p].x;
	r.y = v[p].y;
	sort(v2, v2+nr, comp);
	n = 1;
	v[0].x = r.x;
	v[0].y = r.y;
	v[1].x = v2[0].x;
	v[1].y = v2[0].y;
	for(int i = 1; i< nr; i++)
	{
		f = 0;
		while(f == 0 && n>=1)
		{
			p = v[n-1].x * v[n].y + v[n].x * v2[i].y + v2[i].x*v[n-1].y - v2[i].x*v[n].y - v[n].x * v[n-1].y - v[n-1].x * v2[i].y;
			if(p < 0)
			{
				n--;
			}
			if(p > 0)
			{
				f = 1;
				n++;
				v[n].x = v2[i].x;
				v[n].y = v2[i].y;
			}
		}
	}
	printf("%d\n", n+1);
	for(int i = 0; i<= n; i++) printf("%lf %lf\n", v[i].x, v[i].y);
	fclose(fin);
	fclose(fout);
	return 0;
}