Cod sursa(job #533993)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 februarie 2011 22:16:35
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 100010

int n, x[nmax], y1[nmax], y2[nmax], y[nmax], st[nmax], st2[nmax], pi, v[nmax], pf; 

int cmp(int i, int j)
{
	return (x[i]-x[pi])*(y[j]-y[pi])<(x[j]-x[pi])*(y[i]-y[pi]);
}

int semn(int i1, int i2, int i3)
{
	return x[i1]*y[i2]+x[i2]*y[i3]+x[i3]*y[i1]-y[i1]*x[i2]-y[i2]*x[i3]-y[i3]*x[i1];
}

int semn2(int x1, int y1, int x2, int y2, int xp, int yp)
{
	return xp*(y1-y2)-yp*(x1-x2)+(x1*y2-x2*y1);
}

int main()
{
	freopen("oypara.in","r",stdin);
	freopen("oypara.out","w",stdout);
	scanf("%d",&n);
	int i, j, ok;
	for (i=1; i<=n; i++)
		scanf("%d %d %d",&x[i], &y2[i], &y1[i]);
	x[0]=y[0]=1<<30;
	pi=0;
	for (i=1; i<=n; i++) y[i]=y2[i];
	for (i=1; i<=n; i++)
		if (x[i]<x[pi] || (x[i]==x[pi] && y[i]<y[pi])) pi=i;
	x[0]=y[0]=0;
	pf=0;
	for (i=1; i<=n; i++)
		if (x[i]>x[pf] || (x[i]==x[pf] && y[i]>y[pf])) pf=i;
	v[0]=0;
	for (i=1; i<=n; i++)
		if (i!=pi)
			v[++v[0]]=i;
	sort (v+1, v+v[0]+1, cmp);
	int h2=1;
	st2[1]=pi;
	for (i=1; i<=v[0]; i++)
	{
		while (h2>1 && semn(st2[h2-1], st2[h2], v[i])>0) h2--;
		st2[++h2]=v[i];
		if (v[i]==pf) break;
	}
	
	x[0]=y[0]=0;
	pi=0;
	for (i=1; i<=n; i++) y[i]=y1[i];
	for (i=1; i<=n; i++)
		if (x[i]>x[pi] || (x[i]==x[pi] && y[i]>y[pi])) pi=i;
	x[0]=y[0]=1<<30;
	pf=0;
	for (i=1; i<=n; i++)
		if (x[i]<x[pf] || (x[i]==x[pf] && y[i]<y[pf])) pf=i;
	v[0]=0;
		for (i=1; i<=n; i++)
			if (i!=pi)
				v[++v[0]]=i;
	sort (v+1, v+v[0]+1, cmp);
	int h=1;
	st[1]=pi;
	for (i=1; i<=v[0]; i++)
	{
		while (h>1 && semn(st[h-1], st[h], v[i])>0) h--;
		st[++h]=v[i];
		if (v[i]==pf) break;
	}
	
	j=1;
	i=h2;
	ok=1;
	while (ok)
	{
		ok=0;
		while (semn2(x[st[j]], y1[st[j]], x[st2[i]], y2[st2[i]], x[st2[i-1]], y2[st2[i-1]])<0) i--, ok=1;
		while (semn2(x[st[j]], y1[st[j]], x[st2[i]], y2[st2[i]], x[st[j+1]], y1[st[j+1]])>0) j++, ok=1;
	}
	printf("%d %d %d %d\n", x[st[j]], y1[st[j]], x[st2[i]], y2[st2[i]]);
}