Cod sursa(job #1985396)

Utilizator gabib97Gabriel Boroghina gabib97 Data 27 mai 2017 20:24:20
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define N 120001
using namespace std;

int n, m, s[N], t;
double inf = 1000000005;

struct punct { double x, y; } p[N];

double det(punct p0, punct p1, punct p2)
{
	return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}

double dist(punct p1, punct p2)
{
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}


bool cmp(punct a, punct b)
{
	double d = det(p[1], a, b);
	return  d > 0 || (d == 0 && dist(a, p[1]) < dist(b, p[1]));
}

void solve()
{
	int i;
	double d;

	t = 2;
	s[1] = 1; s[2] = 2;

	for (i = 3; i <= n; i++)
	{
		d = det(p[s[t-1]], p[s[t]], p[i]);
		if (d > 0)
			s[++t] = i;
		else if (d == 0)
			s[t] = i;
		else
		{
			while (det(p[s[t-1]], p[s[t]], p[i]) < 0)
				t--;

			s[++t] = i;
		}
	}
}

int main()
{
	freopen ("infasuratoare.in","r",stdin);
	freopen ("infasuratoare.out","w",stdout);
	scanf("%i", &n);

	double mx = inf, my = inf; 
	int q, i;
	for (i = 1; i <= n; i++)
	{
		scanf("%lf%lf", &p[i].x, &p[i].y);
		if (p[i].y < my || (p[i].y == my && p[i].x < mx)) 
		{
			my = p[i].y; mx = p[i].x;
			q = i;
		}
		
	}
	
	swap(p[1], p[q]);
	sort(p + 2, p + n + 1, cmp);
	solve();

	printf("%i\n", t);
	for (i = 1; i <= t; i++)
		printf("%lf %lf\n", p[s[i]].x, p[s[i]].y);

	return 0;
}