Cod sursa(job #193660)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 5 iunie 2008 22:37:28
Problema Oypara Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.83 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <cassert>

using namespace std;

#define maxN 102400
#define TRACE(x) (cerr << #x << " = " << (x) << endl)

/* linii vertical */
struct liney {
	int x, y1, y2;
};

inline bool operator < (const liney l1, const liney l2)
{
	return l1.x < l2.x;
}

/* puncte */
struct point {
	int x, y;
};

inline bool operator < (const point l1, const point l2)
{
	return l1.x < l2.x;
}

inline long long point_value(const point p3, const point p1, const point p2)
{
	long long line[3];
	
	line[0] = p1.y - p2.y;
	line[1] = p2.x - p1.x;
	line[2] = - p1.x*line[0] - p1.y*line[1];	
	
	return p3.x*line[0] + p3.y*line[1] + line[2];
}

/* date globale */
int N;
vector<liney> pnt;

/* infasuratoare convexa */
void convex_hull(vector<point> &poly)
{
	/* sorting the points after x coordinate */
	// sort(poly.begin(), poly.end());

	assert(poly.size() >= 3);

	vector<int> care;
	vector<bool> used(poly.size(), false);

	/* primul punct e mereu in infasuratoare */	
	care.push_back(0);

	// adaugam punctele 1...(n-1)
	for(int i = 1; i < poly.size(); ++ i) if(!used[i]) {
		while(care.size() >= 2) {
			const int p0 = *(care.end()-1);
			const int p1 = *(care.end()-2);
			long long value = point_value(poly[i], poly[p0], poly[p1]);
			
			if(value < 0) {
				used[p0] = false;
				care.pop_back();
			} else
				break;
		}

		care.push_back(i);
		used[i] = true;
	}

	// adaugam punctele (n-1)...0
	for(int i = poly.size()-1; i >= 0; -- i) if(!used[i]) {
		while(care.size() >= 2) {
			const int p0 = *(care.end()-1);
			const int p1 = *(care.end()-2);
			long long value = point_value(poly[i], poly[p0], poly[p1]);
			
			if(value < 0) {
				used[p0] = false;
				care.pop_back();
			} else
				break;
		}
		
		care.push_back(i);
		used[i] = true;
	}

	// evident 0 o sa fie de 2 ori
	assert(care.back() == 0);
	care.pop_back();
	
	vector<point> result;
	for(int i = 0; i < care.size(); ++ i)
		result.push_back(poly[care[i]]);
	poly = result;

	assert(poly.size() >= 3);
}

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

	scanf("%d", &N);
	for(int i = 0; i < N; ++ i) {
		liney p;
		scanf("%d %d %d", &p.x, &p.y1, &p.y2);
		pnt.push_back(p);
		
		assert(p.y1 < p.y2);
	}
	sort(pnt.begin(), pnt.end());

	vector<point> upp, dop;	
	for(int i = 0; i < N; ++ i) {
		upp.push_back((point) { pnt[i].x, pnt[i].y2 });
		dop.push_back((point) { pnt[i].x, pnt[i].y1 });
	}

	convex_hull(upp);
	TRACE(upp.size());
	convex_hull(dop);
	TRACE(dop.size());

	/*
	cerr << "Top poly\n";
	for(int i = 0; i < upp.size(); ++ i)
		cerr << "(" << upp[i].x << " " << upp[i].y << ") ";
	cerr << endl;

	cerr << "Bottom poly\n";
	for(int i = 0; i < dop.size(); ++ i)
		cerr << "(" << dop[i].x << " " << dop[i].y << ") ";
	cerr << endl;
	*/

	int which;

	// pentru fiecare punct il aflam pe cel mai din dreapta
	which = 0;
	for(int i = 0; i < dop.size(); ++ i) {
		/*
		 * TRACE(i);
		 * TRACE(dop[i].x);
		 * TRACE(dop[i].y);
		 */
		
		// incercam urmatorul
		while(true) {
			const int next = which == upp.size()-1 ? 0 : which+1;
			
			// TRACE(next);
			
			if(point_value(upp[next], dop[i], upp[which]) >= 0)
				break;
			which = next;
		}

		// incercam precendetul
		while(true) {
			const int prev = which == 0 ? upp.size()-1 : which-1;
			if(point_value(upp[prev], dop[i], upp[which]) >= 0)
				break;
			which = prev;
		}

		// cout << "(" << i << " " << dop[i].x << " " << dop[i].y << ") ";
		// cout << "(" << which << " " << upp[which].x << " " << upp[which].y << ")" << endl;

		const int next = i == dop.size()-1 ? 0 : i+1;
		const int prev = i == 0 ? dop.size()-1 : i-1;

		if(point_value(dop[next], dop[i], upp[which]) <= 0 && point_value(dop[prev], dop[i], upp[which]) <= 0) {
			// printf("DA\n");
			printf("%d %d %d %d\n", dop[i].x, dop[i].y, upp[which].x, upp[which].y);
			return 0;
		}
	}
	

	// pentru fiecare punct il aflam pe cel mai din stanga
	which = 0;
	for(int i = 0; i < dop.size(); ++ i) {
		// incercam urmatorul
		while(true) {
			const int next = which == upp.size()-1 ? 0 : which+1;
			if(point_value(upp[next], dop[i], upp[which]) <= 0)
				break;
			which = next;
		}

		// incercam precendetul
		while(true) {
			const int prev = which == 0 ? upp.size()-1 : which-1;
			if(point_value(upp[prev], dop[i], upp[which]) <= 0)
				break;
			which = prev;
		}

		// cout << "(" << i << " " << dop[i].x << " " << dop[i].y << ") ";
		// cout << "(" << which << " " << upp[which].x << " " << upp[which].y << ")" << endl;

		const int next = i == dop.size()-1 ? 0 : i+1;
		const int prev = i == 0 ? dop.size()-1 : i-1;

		if(point_value(dop[next], dop[i], upp[which]) >= 0 && point_value(dop[prev], dop[i], upp[which]) >= 0) {
			// printf("DA\n");
			printf("%d %d %d %d\n", dop[i].x, dop[i].y, upp[which].x, upp[which].y);
			return 0;
		}
	}

	// printf("NU\n");	
	return 0;
}