Cod sursa(job #590701)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 19 mai 2011 15:58:53
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 100005

int N, min1, min2, I1[DIM], I2[DIM];
struct pct { int x, y; } A[DIM], B[DIM];

int modul(int a)
{
	if (a > 0)
		return a;
	return -a;
}

void swap(pct &a, pct &b)
{
	pct x = a;
	a = b;
	b = x; 
}

void swapi(int &a, int &b)
{
	int x = a;
	a = b;
	b = x; 
}

int cmp(pct a, pct b)
{
	int x1 = a.x, x2 = b.x;
	int y1 = a.y, y2 = b.y;
	
	if (x2*y1 != x1*y2)
		return x2*y1 < x1*y2;
	return x1*x1 + y1*y1 < x2*x2 + y2*y2;
}

int cmp1(pct a, pct b)
{
	int x1 = a.x, x2 = b.x;
	int y1 = a.y, y2 = b.y;
	
	return x2*y1 != x1*y2;
}

int adet(pct a, pct b, pct c)
{
	int x1 = a.x, x2 = b.x, x3 = c.x;
	int y1 = a.y, y2 = b.y, y3 = c.y;
	
	return x2*(y3-y1) + x3*(y1-y2) + x1*(y2-y3);
}

void infasoara(pct A[], int I[])
{
	A[N] = A[0];
	for (int i = 0; i < N; i++)
	{
		A[i].x -= A[N].x;
		A[i].y -= A[N].y;
	}
	sort(A + 1, A + N, cmp);
	
	I[0] = 2;
	I[1] = 0, I[2] = 1;
	
	int poz = 1;
	for (int i = 2; i < N; i++)
	{
		while ( adet(A[I[I[0]-1]], A[I[I[0]]], A[i]) <= 0 && I[0] > 2 )
			I[0]--;
		I[++I[0]] = i;
		if ( cmp1(A[I[I[0]]], A[I[I[0]-1]]) )
			poz = I[0];
	}
	for (int i = poz, j = I[0]; i < j; i++, j--)
		swapi(I[i], I[j]);
	I[I[0]+1] = I[1];
	I[I[0]+2] = I[2];
	
	for (int i = 0; i < N; i++)
	{
		A[i].x += A[N].x;
		A[i].y += A[N].y;
	}
}

int main()
{
	freopen("oypara.in", "r", stdin);
	freopen("oypara.out", "w", stdout);
	
	scanf("%d", &N);
	for (int i = 0, x, y1, y2; i < N; i++)
	{
		scanf("%d%d%d", &x, &y1, &y2);
		A[i].x = x, A[i].y = y1;
		if (A[min1].y > A[i].y)
			min1 = i;
		B[i].x = x, B[i].y = y2;
		if (B[min2].y > B[i].y)
			min2 = i;
	}
	
	swap(A[min1], A[0]);
	swap(B[min2], B[0]);
	
	infasoara(A, I1);
	infasoara(B, I2);
	
	int i, j, ok = 1, a1, a2, a3, a4;
	pct Pa, Pb, Pc, Qa, Qb, Qc;
	for (i = 1; i <= I1[0] && ok; i++)
	{
		Pa = A[I1[i]];
		Pb = A[I1[i+1]];
		Pc = A[I1[i+2]];
		
		for (j = 1; j <= I2[0] && ok; j++)
		{
			Qa = B[I2[j]];
			Qb = B[I2[j+1]];
			Qc = B[I2[j+2]];
			
			a1 = adet(Pb, Qb, Pa);
			a2 = adet(Pb, Qb, Pc);
			a3 = adet(Pb, Qb, Qa);
			a4 = adet(Pb, Qb, Qc);
			
			if (a1 > 0 && a2 < 0 || a1 < 0 && a2 > 0)
				continue;			
			if (a3 > 0 && a4 < 0 || a3 < 0 && a4 > 0)
				continue;
			if (a1 == 0)
				swap(a1, a2);
			if (a3 == 0)
				swap(a3, a4);
			if (a1 >= 0 && a3 <= 0 || a1 <= 0 && a3 >= 0)
				ok = 0;
		}
	}
	
	printf("%d %d %d %d\n", A[I1[i]].x, A[I1[i]].y, B[I2[j]].x, B[I2[j]].y);
	
	return 0;
}