Cod sursa(job #649499)

Utilizator tiganu_dolarMancea Catalin tiganu_dolar Data 16 decembrie 2011 11:30:40
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
//1  2  3  4  5  6  7  8  9  10 11 12 13 14
//1  5  4  2  3  	
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pi pair<int,int>
#define x first
#define y second
#define ll long long
#define NMAX 100005

int nr[3],n;
int st[3][NMAX];
pi v[3][NMAX];
char viz[NMAX];

inline int cmp(const pi& a,const pi& b)
{
	if(a.y==b.y)
		return a.x<b.x;
	return a.y<b.y;
}

inline int semn(pi A,pi B,pi C)
{
	ll a=B.y-A.y;
	ll b=A.x-B.x;
	ll c=((ll)B.x*A.y)-((ll)A.x*B.y);
	return a*C.x+b*C.y+c<=0;
}

void infas(int ind)
{
	int i,sf;
	memset(viz,0,sizeof(viz));
	memset(st[ind],0,sizeof(st[ind]));
	
	st[ind][1]=1;st[ind][2]=2;
	sf=2;
	for(i=3;i<=n;i++)
	{
		while(sf>1 && semn(v[ind][st[ind][sf-1]],v[ind][st[ind][sf]],v[ind][i]))
			sf--;
		st[ind][++sf]=i;
	}
	for(i=1;i<=sf;i++)
		viz[st[ind][i]]=1;
	viz[st[ind][1]]=0;
	for(i=n;i>=1;i--)
		if(!viz[i])
		{
			while(sf>1 && semn(v[ind][st[ind][sf-1]],v[ind][st[ind][sf]],v[ind][i]))
				sf--;
			st[ind][++sf]=i;
		}
	nr[ind]=sf;
	st[ind][0]=st[ind][nr[ind]-1];
}



int main ()
{
	int s1,s2,s3,s4,j;
	int i,px,py1,py2;

	freopen("oypara.in","r",stdin);
	freopen("oypara.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&px,&py1,&py2);
		v[1][i]=mp(px,py1);
		v[2][i]=mp(px,py2);
	}
	sort(v[1]+1,v[1]+n+1,cmp);
	sort(v[2]+1,v[2]+n+1,cmp);
	infas(1);	
	infas(2);
	for(i=nr[1];i>=1;i--)
		for(j=1;j<=nr[2];j++)
		{
			s1=semn(v[1][st[1][i]],v[2][st[2][j]],v[1][st[1][i-1]]);	
			s2=semn(v[1][st[1][i]],v[2][st[2][j]],v[1][st[1][i+1]]);
			s3=semn(v[1][st[1][i]],v[2][st[2][j]],v[2][st[2][j-1]]);
			s4=semn(v[1][st[1][i]],v[2][st[2][j]],v[2][st[2][j+1]]);				
			if(s1==s2 && s3==s4 && s1!=s3)
			{
				printf("%d %d %d %d\n",v[1][st[1][i]].x,v[1][st[1][i]].y,v[2][st[2][j]].x,v[2][st[2][j]].y);
				return 0;
			}
		}
	
	
	return 0;
}