#ifndef GC24HELPERS_H_
#define GC24HELPERS_H_

#include <map>

namespace cg24 {

struct point_t {
	double x;
	double y;
};

struct segment_t {
	int id; /* to overcome numerical error when we find a point on an already-known ..
	           .. segment we identify segments with unique ID.
	           binary search with numerical errors is guaranteed to find an index ..
		   .. whose distance from the correct one is O(1) (here it is 2). */

	point_t p; /* after input we compare and swap to guarantee that p.x <= q.x */
	point_t q;

	bool valid() { return p.x <= q.x; }

	/** line: y = ax + b. it is guaranteed that the line is not vertical (a is finite) */
	double a() const { return (p.y - q.y) / (p.x - q.x); }
	double b() const { return p.y - a() * p.x; }

	/** the y-coordinate of the point on the segment whose x-coordinate ..
	   is given. Segment boundaries are NOT enforced here. */
	double calc(double x) const { return a() * x + b(); }
};

bool is_left_turn(const point_t &a, const point_t &b, const point_t &c)
{
	double x1 = a.x, x2 = b.x, x3 = c.x,
		y1 = a.y, y2 = b.y, y3 = c.y;

	return x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) > 0;
}

bool intersects(const segment_t &s1, const segment_t &s2, point_t *pCross)
{
	if ((is_left_turn(s1.p, s1.q, s2.p) != is_left_turn(s1.p, s1.q, s2.q)) &&
		(is_left_turn(s2.p, s2.q, s1.p) != is_left_turn(s2.p, s2.q, s1.q)))
	{
		double a1 = s1.a();
		double a2 = s2.a();

		double b1 = s1.b();
		double b2 = s2.b();

		/* commutation consistency: sort by a (then by b) */
		if (a1 > a2 || (a1 == a2 && b1 > b2))
		{
			double tmp; /* for swap */
			
			tmp = a1; a1 = a2; a2 = tmp; /* swap(a1,a2) */
			tmp = b1; b1 = b2; b2 = tmp; /* swap(b1,b2) */
		}

		/*
		a1x + b1 = y
		a2x + b2 = y
		(a1 - a2)x + (b1-b2) = 0
		x = (b2-b1)/(a1-a2)
		*/

		if (pCross)
		{
			pCross->x = (b2 - b1) / (a1 - a2);
			pCross->y = a1 * pCross->x + b1;
		}

		return true;
	}
	else
	{
		return false;
	}
}

bool intersects(const segment_t& s1, const segment_t& s2)
{
	point_t pVoid;
	return intersects(s1, s2, &pVoid);
}

template<typename T>
class priority_queue {
private:
	struct priority_t {
		double p;
		double p2;
		double p3;
		long long pzm;
		
		priority_t(double p, double p2, double p3, long long pzm) :
			p(p), p2(p2), p3(p3), pzm(pzm)
		{
		}
	};
	
	struct comparator_t {
		bool max1;
		bool max2;
		bool max3;
		
		bool operator()(const priority_t &l, const priority_t &r) const
		{
			if (l.p != r.p)
				return max1 ? (l.p > r.p) : (l.p < r.p);
			
			if (l.p2 != r.p2)
				return max2 ? (l.p2 > r.p2) : (l.p2 < r.p2);
			
			if (l.p3 != r.p3)
				return max3 ? (l.p3 > r.p3) : (l.p3 < r.p3);
			
			return l.pzm < r.pzm;
		}
	};
	
	long long t;
	std::map<priority_t, T, comparator_t> pq;
public:
	priority_queue() : priority_queue(true) { }
	priority_queue(bool max) : priority_queue(max, true) { }
	priority_queue(bool max, bool tiebreakerMax) : priority_queue(max, tiebreakerMax, true) { }
	priority_queue(bool max, bool tiebreakerMax, bool tiebreaker2Max)
	{
		auto cmp = comparator_t();
		cmp.max1 = max;
		cmp.max2 = tiebreakerMax;
		cmp.max3 = tiebreaker2Max;
		t = 0;
		pq = std::map<priority_t, T, comparator_t>(cmp);
	}
	
	void insert(const T &x, double p) { insert(x, p, 0); }
	void insert(const T &x, double p, double tiebreaker) { insert(x, p, tiebreaker, 0); }
	void insert(const T &x, double p, double tiebreaker, double tiebreaker2) { pq[priority_t(p, tiebreaker, tiebreaker2, t++)] = x; }
	
	bool empty() const { return pq.empty(); }
	
	T pop()
	{
		auto ptr = pq.begin();
		T res = ptr->second;
		pq.erase(pq.begin());
		return res;
	}
};

}

#endif