Cod sursa(job #1575384)

Utilizator heracleRadu Muntean heracle Data 21 ianuarie 2016 14:28:48
Problema Oypara Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 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];


void make_dreapta(point a, point b, int &q, int &w, int &e)
{
	q=a.y-b.y;
	w=b.x-a.x;

	e=-a.x*q-a.y*w;
}

void turul2()
{
	int loc=1;

	int q,w,e;

	for(int i=1; i<=super[0]; i++)
	{
		make_dreapta(a[super[i]], b[buna[loc]] , q, w, e);

		if(q*b[buna[loc+1]].x + w*b[buna[loc+1]].y+e <0)
		{
			loc++;
		make_dreapta(a[super[i]], b[buna[loc]] , q, w, e);
		}

		if(q*a[super[i+1]].x + w*b[super[i+1]].y+e <=0)
		{
			fprintf(out,"%d %d %d %d\n", b[buna[loc]].x, b[buna[loc]].y, a[super[i]].x, a[super[i]].y);
			return;
		}
	}
}



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

	turul2();

	return 0;
}