Cod sursa(job #1575778)

Utilizator heracleRadu Muntean heracle Data 21 ianuarie 2016 20:41:09
Problema Oypara Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
#include <algorithm>
#include <unordered_map>

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

std::unordered_map<int, int> mp;

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(b[super[i]], a[buna[loc]] , q, w, e);

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

		if(q*b[super[i+1]].x + w*b[super[i+1]].y+e >=0 && q*b[super[i-1]].x + w*b[super[i-1]].y+e >=0)
		{
			fprintf(out,"%d %d %d %d\n", a[buna[loc]].x, a[buna[loc]].y, b[super[i]].x, b[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;



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

	int x,y1,y2;

	int min=1;

	int cont=0;

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

		if(!mp[x])
		{
			cont++;
			mp[x]=cont;
			a[cont].x=x;
			a[cont].y=y1;

			b[cont].x=x;
			b[cont].y=y2;
		}
		else
		{
			if(y1>a[mp[x]].y)
				a[mp[x]].y=y1;
			if(y2<b[mp[x]].y)
				b[mp[x]].y=y2;
		}
	}

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

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

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

	for(int i=3; i<=cont; 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;
}