Cod sursa(job #1492302)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 27 septembrie 2015 15:54:40
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define DIM 200005
#define infile "rays.in"
#define outfile "rays.out"

std::ifstream fin(infile);
std::ofstream fout(outfile);

struct Segment {

	int x;

	int y1, y2;

	Segment() {}

	Segment(int x, int y1, int y2) {

		this->x = x;
		this->y1 = y1;
		this->y2 = y2;

	}

};

struct Point {

	int x;
	int y;

};

std::vector<Segment> leftSegments, rightSegments;


inline bool comp(const Segment &a, const Segment &b) {

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

}


int main() {

	int n;

	fin >> n;

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

		int x, y1, y2;

		fin >> x >> y1 >> y2;

		if (y1 > y2) {

			std::swap(y1, y2);

		}

		if (x < 0) {

			leftSegments.push_back(Segment(x, y1, y2));

		}
		else {

			rightSegments.push_back(Segment(x, y1, y2));

		}

	}


	int solution = 0;

	if (!leftSegments.empty()) {

		++solution;

		std::sort(leftSegments.begin(), leftSegments.end(), comp);

		Point last;

		last.x = leftSegments[0].x;
		last.y = leftSegments[0].y2;

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

			if (1LL * leftSegments[i].y1 * last.x - 1LL * leftSegments[i].x * last.y > 0) {

				++solution;

				last.x = leftSegments[i].x;
				last.y = leftSegments[i].y2;

			}

		}

	}

	if (!rightSegments.empty()) {

		++solution;

		std::sort(rightSegments.begin(), rightSegments.end(), comp);

		Point last;

		last.x = rightSegments[0].x;
		last.y = rightSegments[0].y2;

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

			if (1LL * rightSegments[i].y1 * last.x - 1LL * rightSegments[i].x * last.y > 0) {

				++solution;

				last.x = rightSegments[i].x;
				last.y = rightSegments[i].y2;

			}

		}

	}


	fout << solution;

	return 0;

}

//Trust me, I'm the Doctor!