Cod sursa(job #1539837)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 1 decembrie 2015 18:20:05
Problema Oypara Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

struct Point {

	int x, y;

	Point() {
		x = 0;
		y = 0;
	}

	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}

	bool operator < (const Point a) const {
		return (x == a.x ? y > a.y : x > a.x);
	}

};

vector<Point> up, down, hullUp, hullDown;

bool convex(const Point &a, const Point &b, const Point &c) {

	return 1LL * (a.x - c.x)*(b.y - c.y) - 1LL * (a.y - c.y)*(b.x - c.x) > 0LL;

}

vector<Point> getConvexHull(vector<Point> points, bool rev) {

	sort(points.begin(), points.end());

	if (rev)
		reverse(points.begin(), points.end());

	vector<Point> hull;
	hull.push_back(points[0]);
	hull.push_back(points[1]);

	for (unsigned int i = 2; i < points.size(); ++i) {

		while (hull.size() > 1 && !convex(hull[hull.size() - 2], hull[hull.size() - 1], points[i]))
			hull.pop_back();

		hull.push_back(points[i]);

	}
	
	return hull;

}

int main() {

	ifstream fin("oypara.in");
	ofstream fout("oypara.out");

	int n;
	fin >> n;

	for (int i = 1; i <= n; ++i) {

		int x, yUp, yDown;
		fin >> x >> yUp >> yDown;

		up.push_back(Point(x, yUp));
		down.push_back(Point(x, yDown));

	}

	hullUp = getConvexHull(up, false);
	hullDown = getConvexHull(down, true);

	Point solUp;
	for (unsigned int i = 0, j = 0; i + 1 < hullUp.size(); ++i) {

		while (j < hullDown.size() && !convex(hullUp[i], hullUp[i + 1], hullDown[j]))
			++j;

		if (j == hullDown.size()) {
			solUp = hullUp[i];
			break;
		}

	}

	Point solDown;
	for (unsigned int i = 0; i + 1 < hullDown.size(); ++i) {
		
		if (!convex(hullDown[i], hullDown[i + 1], solUp)) {
			solDown = hullDown[i];
			break;
		}
	
	}

	fout << solUp.x << ' ' << solUp.y << ' ' << solDown.x << ' ' << solDown.y << '\n';

	return 0;

}

//Trust me, I'm the Doctor!