Cod sursa(job #597593)

Utilizator katakunaCazacu Alexandru katakuna Data 22 iunie 2011 16:16:41
Problema Oypara Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.93 kb
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

#define Nmax 100010

struct punct {
	int x, y;
};

int n, Na, Nb;
punct A[Nmax], B[Nmax];

int determinant (long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
	
	long long A = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	if (A <= 0) return 1;
	return 0;
}

void rezolva () {
	
	int i, j;
	punct Aux[Nmax];
	
	for (i = 2, j = Nb; i <= Nb; i++, j--)
		Aux[i] = B[j];
	for (i = 2; i <= Nb; i++)
		B[i] = Aux[i];

	B[Nb + 1] = B[1]; A[Na + 1] = A[1];

	for (j = 1, i = 1; i <= Na; i++) {
		
		while ( determinant (A[i+1].x, A[i+1].y, B[j+1].x, B[j+1].y, A[i].x, A[i].y)) {
			j++;          
			if ( !determinant ( B[j+1].x, B[j+1].y, B[j].x, B[j].y, A[i].x, A[i].y ) ) {
			
				printf ("%d %d %d %d\n", A[i].x, A[i].y, B[j].x, B[j].y);
				return ;
			}
		}
	}
}

void infasuratoare (punct A[], int &N) {
	
	int i, p, stp = 1;
	int S[Nmax], viz[Nmax];

	memset (viz, 0, sizeof (viz));

	S[1] = 1; S[2] = 2; 
	p = 2; N = 2; viz[2] = 1;
	while (!viz[1]) {
		
		while (viz[p]) {
			p+= stp;
			if (p == n) stp = -1;
		}

		while (N >= 2 && determinant (A[p].x, A[p].y, A[ S[N-1] ].x, A[ S[N-1] ].y, A[ S[N] ].x, A[ S[N] ].y)) {
			viz[ S[N] ] = 0;
			N--;
		}

		S[++N] = p;
		viz[p] = 1;
	}

	N--;
	punct Aux[Nmax];
	for (i = 1; i <= N; i++)
		Aux[i] = A[ S[i] ];
	for (i = 1; i <= N; i++)
		A[i] = Aux[i];
}

bool cmp (const punct &a, const punct &b) {
	
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

void citire () {

	int i, x, y1, y2;
	
	scanf ("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf ("%d %d %d", &x, &y1, &y2);
		B[i].x = A[i].x = x;
		A[i].y = max (y1, y2);
		B[i].y = min (y1, y2);
	}

	sort (A + 1, A + n + 1, cmp);
	sort (B + 1, B + n + 1, cmp);
}

int main () {

	freopen ("oypara.in", "r", stdin);
	freopen ("oypara.out", "w", stdout);
	
	citire ();
	infasuratoare (A, Na);
	infasuratoare (B, Nb);
    rezolva ();

	return 0;
}