Cod sursa(job #536463)

Utilizator chiar_nimeninimeni chiar_nimeni Data 18 februarie 2011 18:24:41
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
# include <stdio.h>
# include <algorithm>


# define eps 1e-12

using namespace std;

struct infas
{
	float x,y;
} v[130000];

int n,i,st[130000],ok[130000];

inline int cmp (int a, int b)
{
	if (a+eps<b) return -1;
	if (b+eps<a) return 1;
	return 0;
}

inline int cmmp (const infas &a, const infas &b)
{
	int r=cmp (a.x,b.x);
	if (r!=0) return r == -1;
	return cmp(a.y,b.y) == -1;
}

inline int semn (infas a, infas b, infas c)
{
	int p1,p2,p3,rez;
	p1=a.y-b.y;
	p2=b.x-b.x;
	p3=a.x*b.y-b.x*a.y;
	rez=(p1*c.x+p2*c.y+p3, 0);
	return rez;
}

int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf ("%d",&n);
for (i=1; i<=n; i++)
	scanf ("%lf %lf", &v[i].x, &v[i].y);
sort (v+1, v+n+1, cmmp);
ok[2]=1;
pz=2;
i=3;
st[1]=1;
st[2]=2;
for (i=3; i<=n; i++)
{
	if (ok[i]==false)
		while (k>=2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
		{
			ok[st[k]]=0;
			k--;
		}
	k++;
	st[k]=i;
	ok[i]=1;
}
for (i=n; i>=1; i--)
{
	if (ok[i]==false)
		while (k>=2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
		{
			ok[st[k]]=0;
			k--;
		}
	k++;
	st[k]=i;
	ok[i]=1;
}
return 0;
}