Cod sursa(job #589686)

Utilizator ChallengeMurtaza Alexandru Challenge Data 13 mai 2011 13:29:05
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.88 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="oypara.in";
const char OutFile[]="oypara.out";
const int MaxN=100111;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s_point
{
	int x,y;
};

int N,mx,my1,my2,sus_ch_count,jos_ch_count;
s_point O,solA,solB,sus[MaxN],jos[MaxN],sus_ch[MaxN],jos_ch[MaxN];

struct cmp
{
	inline bool operator() (const s_point &a, const s_point &b)
	{
		return (1LL*(a.x-O.x)*(b.y-O.y))<(1LL*(b.x-O.x)*(a.y-O.y));
	}
};

inline int semn(const s_point &A, const s_point &B, const s_point &C)
{
	long long det=(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
	if(det<0)
	{
		return -1;
	}
	if(det>0)
	{
		return 1;
	}
	return 0;
}

inline void infasuratoare(s_point *points, s_point *ch, int &count)
{
	O.x=INF;
	O.y=INF;
	int ind=0;
	for(register int i=1;i<=N;++i)
	{
		if(O.y>points[i].y)
		{
			O=points[i];
			ind=i;
		}
		else if(O.y==points[i].y && O.x>points[i].x)
		{
			O=points[i];
			ind=i;
		}
	}
	swap(points[1],points[ind]);
	
	sort(points+2,points+1+N,cmp());
	
	int S[MaxN];
	S[0]=2;
	S[1]=1;
	S[2]=2;
	
	for(register int i=3;i<=N;++i)
	{
		while(S[0]>=2 && semn(points[S[S[0]-1]],points[S[S[0]]],points[i])>=0)
		{
			--S[0];
		}
		S[++S[0]]=i;
	}
	
	count=S[0];
	for(register int i=1;i<=count;++i)
	{
		ch[i]=points[S[i]];
	}
}

inline int leftmost(s_point *points, const int &count)
{
	int ind=0;
	s_point left;
	left.x=INF;
	left.y=INF;
	for(register int i=1;i<=count;++i)
	{
		if(left.x>points[i].x || (left.x==points[i].x && left.y>points[i].y))
		{
			ind=i;
			left=points[i];
		}
	}
	return ind;
}

inline int rightmost(s_point *points, const int &count)
{
	int ind=0;
	s_point right;
	right.x=-INF;
	right.y=-INF;
	for(register int i=1;i<=count;++i)
	{
		if(right.x<points[i].x || (right.x==points[i].x && right.y>
			points[i].y))
		{
			ind=i;
			right=points[i];
		}
	}
	return ind;
}

inline int next(const int &ind, const int &count)
{
	int x=ind+1;
	if(x>count)
	{
		x=1;
	}
	return x;
}

inline int prev(const int &ind, const int &count)
{
	int x=ind-1;
	if(x<1)
	{
		x=count;
	}
	return x;
}

inline bool jos_intersect(int i2)
{
	int i1=prev(i2,jos_ch_count),i3=next(i2,jos_ch_count);
	if(semn(solA,solB,jos_ch[i1])!=semn(solA,solB,jos_ch[i3]))
	{
		return true;
	}
	return false;
}

inline bool good(int josi2,int susi2)
{
	int josi1=prev(josi2,jos_ch_count);
	int josi3=next(josi2,jos_ch_count);
	int joss1=semn(solA,solB,jos_ch[josi1]);
	int joss3=semn(solA,solB,jos_ch[josi3]);
	if(joss1==0)
	{
		joss1=joss3;
	}
	if(joss3==0)
	{
		joss3=joss1;
	}
	if(joss1!=joss3)
	{
		return false;
	}
	
	int susi1=prev(susi2,sus_ch_count);
	int susi3=next(susi2,sus_ch_count);
	int suss1=semn(solA,solB,sus_ch[susi1]);
	int suss3=semn(solA,solB,sus_ch[susi3]);
	if(suss1==0)
	{
		suss1=suss3;
	}
	if(suss3==0)
	{
		suss3=suss1;
	}
	if(suss1!=suss3)
	{
		return false;
	}
	if(joss1==suss1)
	{
		return false;
	}
	return true;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>mx>>my1>>my2;
		if(my1>my2)
		{
			swap(my1,my2);
		}
		sus[i].x=mx;
		sus[i].y=my2;
		jos[i].x=mx;
		jos[i].y=my1;
	}
	fin.close();
	
	infasuratoare(sus,sus_ch,sus_ch_count);
	infasuratoare(jos,jos_ch,jos_ch_count);
	
	for(register int i=1;i<=sus_ch_count;++i)
	{
		for(register int j=1;j<=jos_ch_count;++j)
		{
			solA=sus_ch[i];
			solB=jos_ch[j];
			if(good(j,i))
			{
				goto afis;
			}
		}
	}
	afis:
	/*
	int sus_start=leftmost(sus_ch,sus_ch_count);
	int sus_end=rightmost(sus_ch,sus_ch_count);
	int jos_start=leftmost(jos_ch,jos_ch_count);
	
	int sus_ind=sus_start;
	int jos_ind=jos_start;
	solB=jos_ch[jos_ind];
	solA=sus_ch[sus_ind];
	do
	{
		while(jos_intersect(jos_ind))
		{
			jos_ind=next(jos_ind,jos_ch_count);
			solB=jos_ch[jos_ind];
		}
		if(good(jos_ind,sus_ind))
		{
			break;
		}
		sus_ind=prev(sus_ind,sus_ch_count);
		solA=sus_ch[sus_ind];
	}while(sus_ind!=sus_end);*/
	
	fout<<solB.x<<" "<<solB.y<<" "<<solA.x<<" "<<solA.y;
	fout.close();
	return 0;
}