Cod sursa(job #237258)

Utilizator mariusdrgdragus marius mariusdrg Data 29 decembrie 2008 13:32:47
Problema Infasuratoare convexa Scor Ascuns
Compilator cpp Status done
Runda Marime 1.66 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define mkp make_pair
#define pb push_back

using namespace std;
const int maxn = 1200000;

vector<pair<double,double> > VECT;
double ARIE;
int N,ST[maxn],VER[maxn];


//Semnul verifica ca triunghiul dat este parcurs in ordine invers trigonometrica
double semn(int i1,int i2,int i3)
{
	return VECT[i1].first * VECT[i2].second + VECT[i2].first * VECT[i3].second + VECT[i3].first * VECT[i1].second - VECT[i1].second * VECT[i2].first - VECT[i2].second * VECT[i3].first - VECT[i3].second * VECT[i1].first;
}


int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d\n",&N);
	for(int i = 1; i <= N; ++i)
	{
		double x = 0,y = 0;
		scanf("%lf %lf\n",&x,&y);
		VECT.pb(mkp(x,y));
	}
	//Verific sa fie sortat
	reverse(VECT.begin(),VECT.end());
	if (next_permutation(VECT.begin(),VECT.end())) sort(VECT.begin(),VECT.end());
	ST[ST[0] = 1] = 1; 
	// Prima data cand fac stiva pentru partea din dreapta dreptei (Pjos,Psus)
	for(int i = 2;i <= N; ++i)
	{
		if (VER[i]) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0)
		{
			VER[ST[ST[0]]] = 0; 
			ST[0]--;
		}
		ST[++ST[0]] = i;
		VER[i] = 1;
	}
	// A 2-a oara cand fac stiva pentru partea din stanga dreptei (Pjos,Psus)
	for(int i = N;i; --i)
	{
		if (VER[i]) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1] - 1,ST[ST[0]] - 1,i - 1) > 0){VER[ST[ST[0]]] = 0;ST[0]--;}
		ST[++ST[0]] = i;
		VER[i] = 1;
	}

	printf("%d\n",ST[0] - 1);
	for(int i = 1;i < ST[0]; ++i)
	{
		printf("%lf %lf\n",VECT[ST[i] - 1].first,VECT[ST[i] - 1].second);
	}
	return 0;
}