Cod sursa(job #34396)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 20 martie 2007 18:29:57
Problema Diamant Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.83 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define spct pair<int, int>
#define EPS 0.00001

int N;
int X1, Y1, X2, Y2, X3, Y3;
vector< spct > pct;
vector< bool > used;

int cmp( spct a, spct b )
{
	return (a.y - Y1) * (b.x - X1) < (b.y - Y1) * (a.x - X1);
}

struct treap { int PR, ID, cnt; double val; treap *l, *r; } *NIL, *R1, *R2;

inline void getcnt( treap *&R )
{
	if (R != NIL)
		R -> cnt = R -> l -> cnt + R -> r -> cnt + 1;
}

inline treap * rotate_left( treap *R )
{
	treap *aux = R -> l;
	R -> l = aux -> r; aux -> r = R;
	getcnt(R); getcnt(aux);
	return aux;
}

inline treap * rotate_right( treap *R )
{
	treap *aux = R -> r;
	R -> r = aux -> l; aux -> l = R;
	getcnt(R); getcnt(aux);
	return aux;
}

inline int compare( double val1, int ID1, double val2, int ID2 )
{
	if (val1 - val2 > EPS) return -1;		//val1 > val2 || (val1 == val2 && ID1 < ID2);
	if (val2 - val1 > EPS) return 1;

	if (ID1 < ID2)
		return -1;
	if (ID1 > ID2)
		return 1;
	return 0;
}

inline treap * __insert( treap *R, int PR, int ID, double val )
{
	if (R == NIL)
	{
		R = new treap;
		R -> ID = ID;
		R -> PR = PR;
		R -> val = val;
		R -> cnt = 1;
		R -> l = R -> r = NIL;
		return R;
	}

	if ( compare(val, ID, R -> val, R -> ID) <= 0 )
	{
		R -> l = __insert( R -> l, PR, ID, val );
		if (R -> l -> PR > R -> PR)
			R = rotate_left(R);
	}
	else
	{
		R -> r = __insert( R -> r, PR, ID, val );
		if (R -> r -> PR > R -> PR)
			R = rotate_right(R);
	}
	getcnt(R);
	return R;
}

inline void insert( treap *&R, int ID, int type )
{
	double val;
	if (type == 0)
		if (pct[ID].x - X2 == 0)
			val = 10e100;
		else
			val = ((double)pct[ID].y - Y2) / ((double)pct[ID].x - X2);
	else
		if (X3 - pct[ID].x == 0)
			val = 10e100;
		else
			val = ((double)pct[ID].y - Y3) / ((double)X3 - pct[ID].x);

	R = __insert( R, rand(), ID, val );
}

inline treap * __erase( treap *R, int ID, double val )
{
	if (R == NIL) return R;
	if (R -> l == NIL && R -> r == NIL)
	{
		free(R);
		return NIL;
	}

	if ( compare(val, ID, R -> val, R -> ID) < 0)
	{
		R -> l = __erase( R -> l, ID, val );
		
		getcnt(R -> l); getcnt(R);
		return R;
	}
	if ( compare(val, ID, R -> val, R -> ID) > 0)
	{
		R -> r = __erase( R -> r, ID, val );

		getcnt(R -> r); getcnt(R);
		return R;
	}

	treap *aux; int t;
	if (R -> l -> PR > R -> r -> PR)
		aux = rotate_left(R);
	else
		aux = rotate_right(R);
	
	t = (aux -> r == R);
	
	R = __erase( R, ID, val );
	getcnt(R);
	if (t == 0)
		aux -> l = R;
	else
		aux -> r = R;

	getcnt(aux);
	return aux;
}

inline void erase( treap *&R, int ID, int type )
{
	double val;
	if (type == 0)
		if (pct[ID].x - X2 == 0)
			val = 10e100;
		else
			val = ((double)pct[ID].y - Y2) / ((double)pct[ID].x - X2);
	else
		if (X3 - pct[ID].x == 0)
			val = 10e100;
		else
			val = ((double)pct[ID].y - Y3) / ((double)X3 - pct[ID].x);

	R = __erase( R, ID, val );
}

inline int find( treap *R, int NR )
{
	if (R -> l -> cnt >= NR)
		return find( R -> l, NR );

	if (R -> l -> cnt + 1 == NR)
		return R -> ID;

	return find( R -> r, NR - R -> l -> cnt - 1 );
}

void init()
{
	NIL = new treap;
	NIL -> val = -10e100;
	NIL -> ID = NIL -> PR = -0x3f3f3f3f;
	NIL -> cnt = 0;
	NIL -> l = NIL -> r = NULL;
	R1 = R2 = NIL;
}

void getcoef( int X1, int Y1, int X2, int Y2, long long &A, long long &B, long long &C )
{
	A = Y1 - Y2;
	B = X2 - X1;
	C = (long long)X1 * Y2 - (long long)X2 * Y1;
}

vector<int> tmp1, tmp2;
void printsol()
{
	used.clear(); used.resize(N, false);
	tmp1.clear(); tmp2.clear();

	for (int i = 1; i <= N / 3; i++)
	{
		int id = find(R1, i);
		used[id] = true;
		tmp1.push_back( id );
	}
	for (int i = 1; i <= N / 3; i++)
	{
		int id = find(R2, i);
		used[id] = true;
		tmp2.push_back( id );
	}
	
	for (int i = 0; i < N; i++)
		if (!used[i])
			printf("%d %d ", pct[i].x, pct[i].y);
	printf("\n");
	for (int i = 0; i < N / 3; i++)
		printf("%d %d ", pct[ tmp1[i] ].x, pct[ tmp1[i] ].y );
	printf("\n");
	for (int i = 0; i < N / 3; i++)
		printf("%d %d ", pct[ tmp2[i] ].x, pct[ tmp2[i] ].y );
	printf("\n");
}

int main()
{
	freopen("tri.in", "rt", stdin);
	freopen("tri.out", "wt", stdout);

	init();

	scanf("%d %d %d %d %d %d", &X1, &Y1, &X2, &Y2, &X3, &Y3);

	scanf("%d", &N);

	pct.resize(N);
	for (int i = 0; i < N; i++)
		scanf("%d %d", &pct[i].x, &pct[i].y);

	sort( pct.begin(), pct.end(), cmp );

	for (int i = 0; i < N / 3 - 1; i++)
		insert( R1, i, 0 );
	for (int i = N / 3 - 1; i < N; i++)
		insert( R2, i, 1 );
	
	for (int i = N / 3 - 1; i < 2 * N / 3; i++)
	{
		insert( R1, i, 0 );
		erase( R2, i, 1 );

		int l, r;
		double Xl, Yl, Xr, Yr;

		l = find( R1, N / 3 );
		r = find( R2, N / 3 );

		long long A1, B1, C1, A2, B2, C2, det;
		getcoef( X1, Y1, pct[i].x, pct[i].y, A1, B1, C1 );
		getcoef( X2, Y2, pct[l].x, pct[l].y, A2, B2, C2 );
		det = A1 * B2 - A2 * B1;

		Xl = ((double)B1 * C2 - (double)B2 * C1) / det;
		Yl = ((double)A2 * C1 - (double)A1 * C2) / det;

		getcoef( X1, Y1, pct[i].x, pct[i].y, A1, B1, C1 );
		getcoef( X3, Y3, pct[r].x, pct[r].y, A2, B2, C2 );
		det = A1 * B2 - A2 * B1;

		Xr = ((double)B1 * C2 - (double)B2 * C1) / det;
		Yr = ((double)A2 * C1 - (double)A1 * C2) / det;

		if (Yl < Yr)
		{
			if (R2 -> cnt > N / 3)
			{
				int tmp = find( R2, N / 3 + 1 );
				getcoef( X1, Y1, pct[i].x, pct[i].y, A1, B1, C1 );
				getcoef( X3, Y3, pct[tmp].x, pct[tmp].y, A2, B2, C2 );
				det = A1 * B2 - A2 * B1;

				if (((double)A2 * C1 - (double)A1 * C2) / det > Yl)
					continue;
			}

			printf("%lf %lf\n", Xl, Yl);
			printsol();
			return 0;
		}
		else
		{
			if (R1 -> cnt > N / 3)
			{
				int tmp = find( R1, N / 3 + 1 );
				getcoef( X1, Y1, pct[i].x, pct[i].y, A1, B1, C1 );
				getcoef( X2, Y2, pct[tmp].x, pct[tmp].y, A2, B2, C2 );
				det = A1 * B2 - A2 * B1;

				if (((double)A2 * C1 - (double)A1 * C2) / det > Yr)
					continue;
			}

			printf("%lf %lf\n", Xr, Yr);
			printsol();
			return 0;
		}
	}
	printf("-1\n");

	return 0;
}