Cod sursa(job #363692)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 14 noiembrie 2009 11:09:42
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include<cmath>
#define nMax 120001
#define min 1000000001
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

double x[nMax],y[nMax];
//double V[nMax];
int n,PI,IND[nMax],ST[nMax];

bool cmpf(int i,int j)
{
	return (double)(x[i] - x[PI]) * (y[j] - y[PI]) < (double)(x[j] - x[PI]) * (y[i] - y[PI]); //arctg(x) este strict crescatoare deci putem sorta direct dupa x 
}

long double semn(int i1,int i2,int i3)
{
	return (long double)x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1]; //am desfacut parantezele
}

int punct_ini ()
{
  x[0]=y[0]=min;
  int punct_initial=0;
  for(int i = 1;i <= n; ++i)
	{
		f>>x[i]>>y[i];
		if (x[i] < x[punct_initial] || (x[i] == x[punct_initial] && y[i] < y[punct_initial])) punct_initial = i;
	}
  return punct_initial;
}
  

int main()
{
  f>>n;
	PI = punct_ini ();
	for(int i = 1;i <= n; ++i)
	{
		if (i == PI) continue; 
		IND[++IND[0]] = i;
	}
	sort(IND + 1,IND + IND[0] + 1,cmpf);
	ST[ST[0] = 1] = PI;
	for(int i = 1;i <= IND[0]; ++i)
	{
		if (IND[i] == PI) continue;
		while(ST[0] >= 2 && semn(ST[ST[0] - 1],ST[ST[0]],IND[i]) > 0) --ST[0];
		ST[++ST[0]] = IND[i];
	}
	ST[++ST[0]] = PI;
	g<<ST[0] - 1<<'\n';
	reverse(ST + 1, ST + ST[0] + 1);
	for(int i = 1;i < ST[0]; ++i)
		g<<x[ST[i]]<<" "<<y[ST[i]]<<'\n';
	f.close (); g.close (); return 0;
}