Cod sursa(job #683051)

Utilizator wink.itsgoneDragusanu Ana wink.itsgone Data 19 februarie 2012 21:30:41
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<cstdio>
#include<algorithm>
#define NMAX 120005
#define EPS 1e-12
#define PCT pair<double, double>
#define x first
#define y second
using namespace std;
int N,H;
PCT v[NMAX], P[NMAX];
int st[NMAX], viz[NMAX];
void CIT(),AFIS(),Hull(); inline int CMP(double, double);int CMPHull(const PCT &, const PCT &),SEMN(PCT , PCT , PCT );
int main()
	{ CIT(); Hull(); AFIS(); return 0; }
void CIT()
	{freopen("infasuratoare.in","rt",stdin);
	 scanf("%ld",&N);
	 for(int i=1; i<=N; ++i) scanf("%lf %lf",&v[i].x, &v[i].y);
	}
void AFIS()
	{freopen("infasuratoare.out","wt",stdout);
	 printf("%d\n", H);
	 for (int i = 1; i <= H; ++i) printf("%.6lf %.6lf\n", P[i].x, P[i].y);
	}
inline int CMP(double a, double b)
	{if (a + EPS < b) return -1; if (b + EPS < a) return +1; return 0; }
int CMPHull(const PCT &a, const PCT &b)
	{int r = CMP(a.x, b.x);   if (r != 0) return r == -1;   return CMP(a.y, b.y) == -1; }
int SEMN(PCT a, PCT b, PCT c)
	{double A = a.y-b.y, B = b.x-a.x, C = a.x*b.y - b.x*a.y;  return CMP(A * c.x + B * c.y + C, 0); }
void Hull()
	{int i, k, pas = 1;
	 sort(v+1, v+N+1, CMPHull);
	 viz[2]=1; st[1]=1; st[2]=2; k=2; i=3;
	 while (!viz[1])
		{while (viz[i]) {if(i == N) pas = -1;		i += pas; }
		 while (k >= 2 && SEMN(v[st[k-1]], v[st[k]], v[i]) == -1) viz[st[k--]] = 0;
		 while (k >= 2 && SEMN(v[st[k-1]], v[st[k]], v[i]) == -1) viz[st[k--]] = 0;
		 st[++k] = i; viz[i] = 1;
		}
	 H=k-1;
	 for(i=1; i<=H; ++i) P[i]=v[st[i]];
	 P[H+1]=P[1];
	}