Cod sursa(job #1577077)

Utilizator heracleRadu Muntean heracle Data 23 ianuarie 2016 11:11:41
Problema Oypara Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <cstdio>
#include <map>


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

const int Q=100007, inf=1000002000;

struct point{
	long long x,y;
};

std::map<int, int> up;
std::map<int, int> down;
int n;


void line(point A, point B, long long &a, long long &b, long long &c)
{
	a=A.y-B.y;
	b=B.x-A.x;
	c=-A.x*a-A.y*b;
}


void finise(long long x1, long long y1, long long x2, long long y2)
{
	fprintf(out,"%lld %lld %lld %lld\n",x1,y1,x2,y2);

	long long a,b,c;

	line(point{x1,y1}, point{x2,y2},a,b,c);

	std::map<int, int>::iterator it;

	long long x;

	for(it=up.begin(); it!=up.end(); it++)
	{
		x=it->first;
		y1=down[x];
		y2=up[x];

		if(a*x+b*y1+c > 0 && a*x+b*y2+c > 0)
		{
			while(true);
		}

		if(a*x+b*y1+c < 0 && a*x+b*y2+c < 0)
		{
			while(true);
		}
	}
}

point upper[Q],lower[Q];
int nru,nrl;

void main3()
{
	upper[0].x=upper[1].x;
	upper[0].y=inf;

	upper[nru+1].x=upper[nru].x;
	upper[nru+1].y=inf;

	lower[0].x=lower[1].x;
	lower[0].y=-inf;

	lower[nrl+1].x=lower[nrl].x;
	lower[nrl+1].y=-inf;

	int u=1;

	long long a,b,c;

	for(int d=1; d<=nrl; d++)
	{
		line(lower[d], upper[u],a,b,c);

		while(a*upper[u+1].x+b*upper[u+1].y+c < 0)
		{
			u++;
			line(lower[d], upper[u],a,b,c);
		}

		if(a*lower[d+1].x+b*lower[d+1].y+c <=0 && a*lower[d-1].x+b*lower[d-1].y+c <=0 )
		{
			finise(lower[d].x, lower[d].y, upper[u].x, upper[u].y);
			return;
		}
	}

}

void main2()
{
	std::map<int, int>::iterator it;

	it=up.begin();
	upper[1].x=it->first;
	upper[1].y=it->second;
	it++;
	upper[2].x=it->first;
	upper[2].y=it->second;
	nru=2;

	long long a,b,c;

	long long x,y;

	for(it++; it!=up.end(); ++it)
	{
		line(upper[nru-1], upper[nru],a,b,c);

		x=it->first;
		y=it->second;

		while(a*x+b*y+c <= 0)
		{
			nru--;
			if(nru==1)
				break;
			line(upper[nru-1], upper[nru],a,b,c);
		}
		nru++;
		upper[nru].x=x;
		upper[nru].y=y;
	}

	it=down.begin();
	lower[1].x=it->first;
	lower[1].y=it->second;
	it++;
	lower[2].x=it->first;
	lower[2].y=it->second;
	nrl=2;

	for(it++; it!=down.end(); ++it)
	{
		line(lower[nrl-1],lower[nrl],a,b,c);

		x=it->first;
		y=it->second;

		while(a*x+b*y+c >= 0)
		{
			nrl--;
			if(nrl==1)
				break;
			line(lower[nrl-1],lower[nrl],a,b,c);
		}
		nrl++;
		lower[nrl].x=x;
		lower[nrl].y=y;
	}

	main3();
}

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

    int a,b,c;

    for(int i=1; i<=n; i++)
    {
		fscanf(in,"%d%d%d",&a,&b,&c);

		if(up[a]==NULL)
		{
			up[a]=c;
			down[a]=b;
		}
		else
		{
			if(up[a]>c)
				up[a]=c;
			if(down[a]<b)
				down[a]=b;
		}
    }
    main2();

    return 0;
}