#include "validation.h"

#include <cmath>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

// For FIXED OUTPUT PROBLEMS:
// This program will be called as
// output_validator input < ans
//
// You should verify the grammar of the answer file.
// See input_validator.cpp for information on how to use the Validator class.
// Furthermore you should check simple properties of the answer.

// For DYNAMIC OUTPUT PROBLEMS:
// This program will be called as
// output_validator input answer < team_output
//
// Please check the grammar of the team output using the Validator class.
// See input_validator.cpp for information on how to use the Validator class.
// You should also check the validity of the answer here.
// For example, check that a tree printed by the team is a tree indeed.

// For INTERACTIVE PROBLEMS:
// Write your output validator as usual, but make sure to flush all standard
// output. Call `v.set_WA_handler(lambda)` to gracefully handle failures when
// parsing team output. You could e.g. send a '-1' to the submission to tell it
// to stop running.

// This validator checks for all points on the path:
// - that none of the line segments intersect
// - that the points are not too close (< 1) to each other (except for directly neighbouring points)
// - that the path starts at (0, 0) and ends at (n, m)
// - that the points all lie inside the grid

bool almostEqual(long double x, long double y) {
	return abs(x - y) < 1e-6;
}

// 0 means colinear, 1 means clockwise and 2 means counterclockwise
int orientation(pair<long double, long double> a, pair<long double, long double> b,
                pair<long double, long double> c) {
	long double area =
	    (b.second - a.second) * (c.first - b.first) - (b.first - a.first) * (c.second - b.second);
	if(almostEqual(area, 0)) {
		return 0;
	}

	return (area > 0) ? 1 : 2;
}

// Segment 1 has points (p1, q1) and Segment 2 has points (p2, q2)
bool segmentsIntersect(pair<long double, long double> p1, pair<long double, long double> q1,
                       pair<long double, long double> p2, pair<long double, long double> q2) {
	int o1 = orientation(p1, q1, p2);
	int o2 = orientation(p1, q1, q2);
	int o3 = orientation(p2, q2, p1);
	int o4 = orientation(p2, q2, q1);

	if(o1 == 0 or o2 == 0 or o3 == 0 or o4 == 0) return false;

	if(o1 != o2 && o3 != o4) return true;
	// We assume that colinear segments do not intersect; we already check that they points do not
	// lie close to each other
	return false;
}

long double pointDistance(pair<long double, long double> point1,
                          pair<long double, long double> point2) {
	long double xDiff = point2.first - point1.first;
	long double yDiff = point2.second - point1.second;
	return sqrt(xDiff * xDiff + yDiff * yDiff);
}

string pointToStr(pair<long double, long double> point) {
	ostringstream buf;
	buf << fixed << setprecision(12);
	buf << "(" << point.first << "," << point.second << ")";
	return buf.str();
}

optional<string> noPointsTooClose(const vector<pair<long double, long double>>& coordinates) {
	for(int i = 0; i < coordinates.size() - 1; i++) {
		for(int j = 0; j < coordinates.size() - 1; j++) {
			// Skip consecutive points
			if(j >= i - 1 && j <= i + 1) {
				continue;
			}
			long double distance = pointDistance(coordinates[i], coordinates[j]);
			if(distance < 1 - 1e-6) {
				return pointToStr(coordinates[i]) + " and " + pointToStr(coordinates[j]) +
				       "lie too close to each other";
			}
		}
	}
	return nullopt;
}

optional<string> noOverlappingSegments(const vector<pair<long double, long double>>& coordinates) {
	for(int i = 0; i < coordinates.size() - 1; i++) {
		auto start_i = coordinates[i];
		auto end_i   = coordinates[i + 1];

		for(int j = 0; j < coordinates.size() - 1; j++) {
			// Skip consecutive segments
			if(j >= i - 1 && j <= i + 1) {
				continue;
			}

			auto start_j = coordinates[j];
			auto end_j   = coordinates[j + 1];

			if(segmentsIntersect(start_i, end_i, start_j, end_j)) {
				return "Segment1(" + pointToStr(start_i) + "," + pointToStr(end_i) + "), " +
				       "Segment2(" + pointToStr(start_j) + "," + pointToStr(end_j) + ")";
			}
		}
	}
	return nullopt;
}

long double calcLength(const vector<pair<long double, long double>>& coordinates) {
	long double totalLength = 0;
	for(int i = 0; i < coordinates.size() - 1; i++) {
		totalLength += pointDistance(coordinates[i], coordinates[i + 1]);
	}
	return totalLength;
}

int main(int argc, char** argv) {
	cout << fixed << setprecision(7);
	cerr << fixed << setprecision(7);

	// The testcase .in file.
	std::ifstream in(argv[1]);
	// The testcase .ans file, if needed for custom validation.
	std::ifstream ans(argv[2]);
	OutputValidator v(argc, argv);

	int input_n, input_m;
	long double input_l;
	in >> input_n >> input_m >> input_l;

	int p = v.read_integer("p", 2, 500);
	v.newline();
	vector<pair<long double, long double>> coordinates;

	for(int i = 0; i < p; i++) {
		long double x_i = v.read_float("x_i", 0, input_n);
		v.space();
		long double y_i = v.read_float("y_i", 0, input_m);
		coordinates.emplace_back(x_i, y_i);
		v.newline();
	}

	int start_x = coordinates[0].first;
	int start_y = coordinates[0].second;
	v.check(almostEqual(start_x, 0) && almostEqual(start_y, 0),
	        "Output path should start at (0,0), but started at (", start_x, ",", start_y, ")");

	int end_x = coordinates[coordinates.size() - 1].first;
	int end_y = coordinates[coordinates.size() - 1].second;
	v.check(almostEqual(end_x, input_n) && almostEqual(end_y, input_m),
	        "Output path should end at (", input_n, ",", input_m, "), but ended at (", end_x, ",",
	        end_y, ")");

	long double foundLength = calcLength(coordinates);
	// first check absolute error < 10^-6, then relative error < 10^-6
	v.check(almostEqual(foundLength, input_l) or almostEqual(foundLength / input_l, 1.0),
	        "Output path has length ", foundLength, ", should have length ", input_l);

	optional<string> closeErrorMessage = noPointsTooClose(coordinates);
	v.check(!closeErrorMessage.has_value(),
	        "Output path has non-consecutive points within distance 1 of each other: ",
	        closeErrorMessage.value_or("none"));

	optional<string> overlapErrorMessage = noOverlappingSegments(coordinates);
	v.check(!overlapErrorMessage.has_value(), "Output path has intersecting segments",
	        overlapErrorMessage.value_or("none"));
}