Cod sursa(job #1569057)

Utilizator heracleRadu Muntean heracle Data 14 ianuarie 2016 22:12:40
Problema Oypara Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>
#include <algorithm>

FILE* in=fopen("oypara.in","r");
FILE* out=fopen("oypara.out","w");

const int Q=100007;

struct point{
	int x,y;
}  a[Q], b[Q];

int buna[Q],super[Q];

bool cmp(const point &f, const point &g)
{
	return f.x<g.x;
}


int clock(const point &u,const point &f, const point &g)
{
	if((f.x-u.x)*(g.y-u.y)-(f.y-u.y)*(g.x-u.x) > 0)
		return 1;
	if((f.x-u.x)*(g.y-u.y)-(f.y-u.y)*(g.x-u.x) < 0)
		return -1;
	return 0;
}

int n;

void finise(point a, point b)
{
	fprintf(out,"%d %d %d %d",a.x,a.y,b.x,b.y);
}

int main()
{
	fscanf(in,"%d",&n);

	int x,y1,y2;

	int min=1;

	for(int i=1; i<=n; i++)
	{
		fscanf(in,"%d%d%d",&x,&y1,&y2);
		a[i].x=x;
		a[i].y=y1;

		b[i].x=x;
		b[i].y=y2;

	}

	std::sort(a+1,a+n,cmp);
	std::sort(b+1,b+n,cmp);

	buna[0]=2;
	buna[1]=1;
	buna[2]=2;

	super[0]=2;
	super[1]=1;
	super[2]=2;

	for(int i=3; i<=n; i++)
	{
		while(buna[0]>=2 && clock(a[buna[buna[0]-1]], a[buna[buna[0]] ], a[i]) !=-1)
			buna[0]--;
		buna[++buna[0]]=i;

		while(super[0]>=2 && clock(b[super[super[0]-1]],b[super[super[0]]],b[i])!=1)
			super[0]--;
		super[++super[0]]=i;
	}

	int A=1, B=1;

	while(A<buna[0] && B<super[0])
	{
		if(clock(a[buna[A]],b[super[B]],b[super[B+1]])!=-1)
		{
			finise(a[buna[A]],b[super[B]]);
			return 0;
		}
		if(clock(a[buna[A]],a[buna[A+1]],b[super[B+1]])==1)
		{
			B++;
		}
		else
		{
			A++;
		}
	}
	finise(a[buna[A]],b[super[B]]);

	return 0;
}