Cod sursa(job #534024)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 14 februarie 2011 23:18:51
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 100010
#define ll long long

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

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

long long 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];
}

ll semn2(ll x1, ll y1, ll x2, ll y2, ll xp, ll 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("%lld %lld %lld",&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;
	}
	reverse(st+1, st+h+1);
	
	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("%lld %lld %lld %lld\n", x[st2[i]], y2[st2[i]], x[st[j]], y1[st[j]]);
}