/*
    hm.cpp - a homework assgnment
    Write a program that:
    - reads segments from a file,
    - moves them to the origin,
    - sorts them by angle and distance,
    - computes the points in the convex hull,
    - computes the area of the convex hull;

    author: Krasimir Georgiev (comco), FN. 80512.
    date: Jun, 2011.
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <complex>
#include <cmath>
#include <cassert>
using namespace std;

typedef double scalar;
typedef complex<scalar> point;
typedef pair<point, point> segment;
vector<segment> read_segments(istream& input) {
	unsigned n; input >> n;
	vector<segment> segments(n);
	for (unsigned i = 0; i < n; ++i) {
		scalar ax, ay, bx, by;
		input >> ax >> ay >> bx >> by;
		point a(ax, ay), b(bx, by);
		segments[i] = segment(a, b);
	}

	return segments;
}

vector<point> translate_to_origin(vector<segment> const& segments) {
	unsigned n = segments.size();
	vector<point> vectors(n);
	for (unsigned i = 0; i < n; ++i) {
		vectors[i] = segments[i].second - segments[i].first;
	}

	return vectors;
}

class point_comparator {
	vector<point> const& vectors;

public:
	point_comparator(vector<point> const& vectors)
		: vectors(vectors) { }

	bool operator()(int id_a, int id_b) const {
		point const& a = vectors[id_a];
		point const& b = vectors[id_b];
		scalar angle_a = arg(a);
		scalar angle_b = arg(b);
		if (angle_a < angle_b) {
			return true;
		}
		else if (angle_a > angle_b) {
			return false;
		}
		else {
			return norm(a) < norm(b);
		}
	}
};

void sort_vectors(vector<point> const& vectors, vector<int>& indices) {
	point_comparator by_angle_length(vectors);
	sort(indices.begin(), indices.end(), by_angle_length);
}

inline scalar det(point const& a, point const& b) {
	return real(a)*imag(b) - imag(a)*real(b);
}

inline bool left(point const& a, point const& b, point const& c) {
	return det(b - a, c - a) > 0;
}
// Graham scan
vector<int> convex_hull(vector<point> const& vectors, vector<int> const& indices) {
	unsigned n = vectors.size();
	if (n < 3) {
		return indices;
	}

	vector<int> hull_vectors;
	hull_vectors.push_back(indices[0]);
	hull_vectors.push_back(indices[1]);
	for (unsigned i = 2; i < n; ++i) {
		point p = vectors[indices[i]];
		while (hull_vectors.size() > 2 &&
         !left(vectors[hull_vectors[hull_vectors.size() - 2]],
               vectors[hull_vectors[hull_vectors.size() - 1]], p)) {
			hull_vectors.pop_back();
		}

		hull_vectors.push_back(indices[i]);
	}

	return hull_vectors;
}

void write_points_at_indices(ostream& output, vector<point> const& points, vector<int> const& indices) {
	unsigned n = indices.size();
	for (int i = 0; i < n; ++i) {
		output << indices[i] << " : " << real(points[i]) << ", " << imag(points[i]) << endl;
	}
}

scalar polygon_area(vector<point> const& points, vector<int> const& indices) {
	unsigned n = indices.size();
	scalar result = 0.0;

	for(unsigned i = 0; i < n; ++i) {
		unsigned j = (i + 1) % n;
		result += det(points[indices[i]], points[indices[j]]);
	}

	result *= 0.5;
	return result;
}

int main() {
    cout << "Format of the input data: " << endl;
    cout << "First line: n - the number of segments; " << endl;
    cout << "Next n lines: 4 double numbers, representing the coordinates of " << endl;
    cout << "two points, describing a segment" << endl;
	cout << "Enter a filename containing point pairs: ";
	char filename[64];
	cin >> filename;
	ifstream input(filename);
	assert(input.good());

	vector<segment> segments = read_segments(input);
	input.close();
	unsigned n = segments.size();
	vector<point> points = translate_to_origin(segments);
	vector<int> indices(n);
	for (int i = 0; i < n; ++i) {
		indices[i] = i;
	}

	cout << "Segments translated to the origin: " << endl;
	write_points_at_indices(cout, points, indices);
	// could support writing the result to a file by
	// changing the first argument to an ofstream

	sort_vectors(points, indices);
	cout << "Sorted segments (angle, then distance to the origin): " << endl;
	write_points_at_indices(cout, points, indices);

	vector<int> hull_points = convex_hull(points, indices);
	cout << "Points on the convex hull: " << endl;
	write_points_at_indices(cout, points, hull_points);

	// Always non-negative - the convex hull is generated ccw
	scalar area = polygon_area(points, hull_points);
	cout << "Area of the convex hull: " << area << endl;

	return 0;
}