Cod sursa(job #695559)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 februarie 2012 13:02:39
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <stdio.h>
#include <algorithm>
#define pdd pair <double,double>
#define x first
#define y second
#define NMAX 100005
#define eps 0.000001
using namespace std;
int n,r,t;
pdd A[NMAX],B[NMAX],C[NMAX],D[NMAX],aux[NMAX];
bool sol=1;
void read()
{
	scanf("%d",&n);
	int i,a,b,c;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		A[i].x=a; A[i].y=b;
		B[i].x=a; B[i].y=c;
	}
}
inline int semn(pdd a,pdd b,pdd c)
{
	double A=a.y-b.y;
	double B=b.x-a.x;
	double C=a.x*b.y-b.x*a.y;
	double val=(A*c.x+B*c.y+C);
	return (val<eps);
}
void prepare()
{
	int i;
	double a1,b1,c1,val;
	a1=A[1].y-A[n].y; 
	b1=A[n].x-A[1].x;
	c1=A[1].x*A[n].y-A[n].x*A[1].y;
	C[++r]=A[1];
	for (i=2; i<n; i++)
	{
		val=A[i].x*a1+A[i].y*b1+c1;
		if (val>eps)
		{
			while (r>=2 && semn(C[r-1],C[r],A[i])) r--;
			C[++r]=A[i];
		}
	}
	while (r>=2 && semn(C[r-1],C[r],A[n])) r--;
	C[++r]=A[n];
	
	a1=B[1].y-B[n].y;
	b1=B[n].x-B[1].x;
	c1=B[1].x*B[n].y-B[n].x*B[1].y;
	D[++t]=B[1];
	for (i=2; i<n; i++)
	{
		val=B[i].x*a1+B[i].y*b1+c1;
		if (val+eps<0)
		{
			while (t>=2 && semn(D[t-1],D[t],B[i])) t--;
			D[++t]=B[i];
		}
	}
	while (t>=2 && semn(D[t-1],D[t],B[n])) t--;
	D[++t]=B[n];
}
void solve()
{
	int i,pas=1,poz=0,st;
	for (i=1; i<t; i++)
		if (semn(C[1],C[2],D[i])!=semn(C[1],C[2],D[i+1]))
		{
			poz=i;
			break ;
		}
	if (poz==0)
	{
		printf("%d %d %d %d\n",(int)C[1].x,(int)C[1].y,(int)C[2].x,(int)C[2].y);
		return ;
	}
	bool ok;
	for (i=2; i<r; i++)
	{
		st=poz; 
		ok=1;
		
		while (1)
		{
			if (poz==0 || poz==t)
			{
				pas*=-1;
				break ;
			}
			if (semn(C[i],C[i+1],D[poz])!=semn(C[i],C[i+1],D[poz+1]))
			{
				ok=0;
				break ;
			}
			poz+=pas;
		}
		
		if (ok)
		{
			poz=st;
			while (1)
			{
				if (poz==0 || poz==t)
				{
					pas*=-1;
					break ;
				}
				if (semn(C[i],C[i+1],D[poz])!=semn(C[i],C[i+1],D[poz+1]))
				{
					ok=0;
					break ;
				}
				poz+=pas;
			}
			if (ok)
			{
				printf("%d %d %d %d\n",(int)C[i].x,(int)C[i].y,(int)C[i+1].x,(int)C[i+1].y);
				return ;
			}
		}
	}
	sol=0;
}
void schimba()
{
	int i,c;
	for (i=1; i<=r; i++)
		aux[i]=C[i];
	c=r; r=t;
	for (i=1; i<=r; i++)
		C[i]=D[i];
	t=c;
	for (i=1; i<=t; i++)
		D[i]=aux[i];
}
int main()
{
	freopen("oypara.in","r",stdin);
	freopen("oypara.out","w",stdout);
	read();
	sort(A+1,A+n+1);
	sort(B+1,B+n+1);
	prepare();
	solve();
	if (sol)
		return 0;
	schimba();
	solve();
	return 0;
}