Cod sursa(job #743609)

Utilizator federerUAIC-Padurariu-Cristian federer Data 5 mai 2012 11:45:16
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<algorithm>
#define Nmax 120002
#define INF 1<<30
using namespace std;



int ST[Nmax], nxt[Nmax];

struct punct {double x, y;};
punct a[Nmax];
int N, P, i;

inline bool cmp(int i, int j)
{return (a[i].x - a[P].x) * (a[j].y - a[P].y) < (a[j].x - a[P].x) * (a[i].y - a[P].y);}
inline double semn(int i1, int i2, int i3)
{	return a[i1].x * a[i2].y + a[i3].x * a[i1].y + a[i2].x * a[i3].y - a[i3].x * a[i2].y - a[i2].x * a[i1].y - a[i1].x * a[i3].y;}

void rezolva()
{		
	a[P].x = a[P].y = INF;
	for(int i=1; i<=N; ++i)
		if(a[i].x < a[P].x || (a[i].x == a[P].x && a[i].y < a[P].y))
			P = i;
	for(int i =1; i<=N; ++i)
		if(i != P)
			nxt[++nxt[0]] = i;
	sort(nxt+1, nxt + nxt[0] + 1, cmp);	
	ST[++ST[0]] = P;
	for(int i=1; i<=nxt[0]; ++i)
	{
		if(nxt[i] == P)
			continue;
		while(ST[0] >= 2 && semn(ST[ST[0]-1], ST[ST[0]], nxt[i]) > 0)
			ST[0]--;
		ST[++ST[0]] = nxt[i];
	}	
}

void afisare()
{
  
freopen("infasuratoare.out", "w", stdout);
  printf("%d\n", ST[0]);
  reverse(ST+1, ST + ST[0] + 1);
  for(i=1;i<=ST[0];++i)
    printf("%lf %lf\n", a[ST[i]].x, a[ST[i]].y);
}

int main()
{
  
  freopen("infasuratoare.in", "r", stdin);
  scanf("%d", &N);
  for(i=1;i<=N;++i)
    scanf("%lf %lf", &a[i].x, &a[i].y);
      
  rezolva();
  afisare();
  fclose(stdin);
  fclose(stdout);
  return 0;
}