#include "Graphics.h"
#include "StdAfx.h"
#include "GF.h"
#include <functional>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <string>
#include <string.h>
#include <random>
#include <iostream>

#define all(x) (x).begin(),(x).end()

#ifndef M_PI
const double M_PI = 3.1415926535897932384626433832795;
#endif

const char CONVEX = 1;
const char COMPLEX = 2;
const char NONCONVEX = 3;

std::mt19937 rng(59);

class TPoint;
void DrawLine(TPoint a, TPoint b, const RGBPIXEL& color);
void DrawLine(int x0, int y0, int x1, int y1, const RGBPIXEL& color);
bool Intersect(const TPoint& a, const TPoint& b, const TPoint& c, const TPoint& d);
int SignArea(const TPoint& a, const TPoint& b, const TPoint& c);

class TPoint {
public:
	int x, y;
	TPoint(int x = 0, int y = 0)
		: x(x)
		, y(y)
	{
	}

	TPoint(const TPoint& a, const TPoint& b)
		: x(b.x - a.x)
		, y(b.y - a.y)
	{
	}

	double Length() {
		return hypot(x, y);
	}

	TPoint operator + (const TPoint& o) {
		return TPoint(x + o.x, y + o.y);
	}

	TPoint operator - (const TPoint& o) {
		return TPoint(x - o.x, y - o.y);
	}

private:

};

class TPolygon {
public:
	TPolygon(int n)
		: n(n)
		, p(std::vector<TPoint>(n))
	{
	}

	void SetRandomPoint(int index, int w, int h) {
		if (index >= 0 && index < n) {
			p[index].x = rng() % w;
			p[index].y = rng() % h;
		}
	}

	void SetRandom(int w, int h) {
		for (int i = 0; i < n; i++) {
			SetRandomPoint(i, w, h);
		}
	}

	void Draw(const RGBPIXEL& color) {
		for (int i = 0; i < n; i++) {
			DrawLine(p[i].x, p[i].y, p[(i + 1) % n].x, p[(i + 1) % n].y, color);
		}
	}

	// should be with multithreading
	void Fill(TPoint minPoint, TPoint maxPoint, RGBPIXEL color, const std::function<bool(TPoint)>& f) {
		for (int x = minPoint.x; x <= maxPoint.x; x++) {
			for (int y = minPoint.y; y <= maxPoint.y; y++) {
				if (f({x, y})) {
					gfSetPixel(x, y, color);
				}
			}
		}
	}

	int Size() const {
		return n;
	}

	TPoint& operator [] (int i) {
		i %= n;
		if (i < 0) i += n;
		return p[i];
	};

	TPoint* begin() {
		return &p[0];
	}

	TPoint* end() {
		return std::next(&p.back());
	}

	bool IsComplex() {
		if (n <= 3) {
			return false;
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 2; j < n; j++) {
				if (j == n - 1 && i == 0) continue;
				if (Intersect(p[i], p[i + 1], p[j], p[j + 1])) {
					return true;
				}
			}
		}
		return false;
	}

	bool IsConvex() {
		if (n <= 3) {
			return true;
		}
		if (IsComplex()) {
			return false;
		}
		int pos = 0;
		int neg = 0;
		for (int i = 0; i < n; i++) {
			const int s = SignArea(p[i - 1 + n], p[i], p[i + 1]);
			if (s > 0) {
				pos++;
			}
			if (s < 0) {
				neg++;
			}
			if (pos > 0 && neg > 0) {
				return false;
			}
		}
		if (pos > 0 && neg > 0) {
			return false;
		}
		return true;
	}

	char Classify() {
		if (IsConvex()) {
			return CONVEX;
		} else if (IsComplex()) {
			return COMPLEX;
		} else {
			return NONCONVEX;
		}
	}

private:
	int n;
	std::vector<TPoint> p;
};

void DrawLine(int x0, int y0, int x1, int y1, const RGBPIXEL& color) {
	const int deltaX = abs(x0 - x1);
	const int deltaY = abs(y0 - y1);
	const int signX = x0 < x1 ? 1 : -1;
	const int signY = y0 < y1 ? 1 : -1;
	int d = deltaX - deltaY;
	gfSetPixel(x1, y1, color);
	while (x0 != x1 || y0 != y1) {
		gfSetPixel(x0, y0, color);
		const int d2 = d << 1;
		if (d2 > -deltaY) { // d > -dy / 2
			d -= deltaY;
			x0 += signX;
		}
		if (d2 < deltaX) {
			d += deltaX;
			y0 += signY;
		}
	}
}

void DrawLine(TPoint a, TPoint b, const RGBPIXEL& color) {
	DrawLine(a.x, a.y, b.x, b.y, color);
}

inline bool cw (const TPoint& a, const TPoint& b, const TPoint& c) { // clockwise
	return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

int sign(int a) {
	if (a > 0) return 1;
	if (a < 0) return -1;
	return 0;
}

inline int SignArea (const TPoint& a, const TPoint& b, const TPoint& c) {
	return sign((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}

inline int Area (const TPoint& a, const TPoint& b) {
	return a.x * b.y - a.y * b.x;
}

inline bool Intersect_1 (int a, int b, int c, int d) {
    if (a > b)  std::swap (a, b);
    if (c > d)  std::swap (c, d);
    return max(a,c) <= min(b,d);
}

bool Intersect (const TPoint& a, const TPoint& b, const TPoint& c, const TPoint& d) {
	return Intersect_1 (a.x, b.x, c.x, d.x)
           && Intersect_1 (a.y, b.y, c.y, d.y)
           && SignArea(a,b,c) * SignArea(a,b,d) <= 0
           && SignArea(c,d,a) * SignArea(c,d,b) <= 0;
}

inline RGBPIXEL RandColor() {
	return RGBPIXEL(rand() % 256, rand() % 256, rand() % 256);
}

bool PointInPolygonWithEvenOddRule(TPolygon& p, const TPoint& a) {
	bool counter = 0;
	const int inf = 2000;
	TPoint b = { a.x, a.y - inf };
	bool pre = false;
	bool cur = false;
	const int n = p.Size();
	for (int i = 0; i < n; i++) {
		cur = Intersect(p[i], p[(i + 1) % n], a, b);
		if (cur && pre && p[i].x == a.x) {
			if ((p[(i - 1 + n) % n].x > a.x) ^ (p[(i + 1) % n].x > a.x)) {
				continue;
			}
		}
		counter ^= cur;
		pre = cur;
	}
	return counter;
}

bool PointInPolygonWithNonZeroWindingRule(TPolygon& p, const TPoint& a) {
	int counter = 0;
	const int inf = 2000;
	TPoint b = { a.x, a.y - inf };
	bool pref = false;
	bool cur = false;
	const int n = p.Size();
	for (int i = 0; i < n; i++) {
		if (cur = Intersect(p[i], p[(i + 1) % n], a, b)) {
			if (cur && pref && p[i].x == a.x) {
				if ((p[(i - 1 + n) % n].x > a.x) ^ (p[(i + 1) % n].x > a.x)) {
					continue;
				}
			}
			if (SignArea(p[i], p[(i + 1) % n], a) >= 0) {
				counter++;
			} else {
				counter--;
			}
		}
		pref = cur;
	}
	return counter;
}

const TCHAR* GetTextForDraw(const std::string s) {
	char* answer = new char[s.size() + 1];
	for (int i = 0; i < s.size(); i++) {
		answer[i] = s[i];
	}
	answer[s.size()] = '\0';
	return answer;
}

template<typename T>
const TCHAR* GetTextForDraw(const T& value) {
	return GetTextForDraw(std::to_string(value));
}

std::pair<TPoint, TPoint> MinMaxBorders(TPolygon& polygon) {
	const int inf = 1 << 30;
	TPoint minPoint = {inf, inf};
	TPoint maxPoint = {-inf, -inf};
	for (const auto& p : polygon) {
		minPoint.x = min(minPoint.x, p.x);
		minPoint.y = min(minPoint.y, p.y);
		maxPoint.x = max(maxPoint.x, p.x);
		maxPoint.y = max(maxPoint.y, p.y);
	}
	return {minPoint, maxPoint};
}

long long DistQrt(const TPoint& a, const TPoint& b) {
	return static_cast<long long>(a.x - b.x) * (a.x - b.x) + static_cast<long long>(a.y - b.y) * (a.y - b.y);
}

long long C(int n, int m) {
	long long answer = 1;
	for (int i = n - m + 1; i <= n; i++) {
		answer *= i;
	}
	for (int i = 1; i <= m; i++) {
		answer /= i;
	}
	return answer;
}

using namespace std;

void DrawBezierLine (std::vector<TPoint>& arr, const RGBPIXEL& color) {
	const int n = arr.size();
	if (n <= 2) {
		DrawLine(arr[0], arr.back(), color);
		return;
	}
	auto dist = [&] (const TPoint& a) {
		return abs(a.x) + abs(a.y);
	};
	long long D = 0;
	for (int i = 2; i < n; i++) {
		D = max(D, dist(arr[i - 2] - arr[i - 1] - arr[i - 1] + arr[i]));
	}
	double N = 1 + sqrt(3 * D);
	double dt = 1 / N;
	auto R = [&] (double t) {
		double x = 0;
		double y = 0;
		for (int i = 0; i < n; i++) {
			double k = C(n, i) * pow(t, i) * pow(1 - t, n - i);
			x += arr[i].x * k;
			y += arr[i].y * k;

		}
		return TPoint(x + 0.5, y + 0.5);
	};
	cout << "here" << endl;
	std::vector<TPoint> a;
	for (double t = 0; t < 1; t += dt) {
		a.push_back(R(t));
	}
	for (int i = 1; i < a.size(); i++) {
		DrawLine(a[i - 1], a[i], color);
	}
}

/*
	de Kasteljo
*/
void DrawBezierLine2(std::vector<TPoint>& arr, const RGBPIXEL& color) {
	const int n = arr.size();
	if (n <= 2) {
		DrawLine(arr[0], arr.back(), color);
		return;
	}
	const int bits = 5;
	const int size = 1 << bits;
	const int halfsize = 1 << (bits - 1);
	std::function<TPoint(const TPoint&, const TPoint&, int)> get = [&] (const TPoint& a, const TPoint& b, int pr) {
		return TPoint(a.x + (pr * (b.x - a.x) + halfsize >> bits), a.y + (pr * (b.y - a.y) + halfsize >> bits));
	};

	std::function<TPoint(std::vector<TPoint>, int)> findPoint = [&] (std::vector<TPoint> a, int pr) {
		if (a.size() <= 2) {
			return get(a[0], a.back(), pr);
		} else {
			for (int i = 0; i + 1 < a.size(); i++) {
				a[i] = get(a[i], a[i + 1], pr);
			}
			a.pop_back();
			return findPoint(a, pr);
		}
	};

	std::vector<TPoint> result;

	for (int t = 0; t <= size; t++) {
		result.push_back(findPoint(arr, t));
	}
	for (int i = 0; i + 1 < result.size(); i++) {
		DrawLine(result[i], result[i + 1], color);
	}

}

bool gfInitScene() {
	try {
		const int WINDOW_SIZE = 800;
		gfSetWindowSize(WINDOW_SIZE, WINDOW_SIZE);
		const int n = 5;
		TPolygon arr(n);
		arr.SetRandom(WINDOW_SIZE, WINDOW_SIZE);
		std::vector<TPoint> kek;
		for (int i = 0; i < n; i++) {
			kek.push_back(arr[i]);
		}
		arr.Draw(RGBPIXEL::Yellow());
		DrawBezierLine(kek, RGBPIXEL::Green());
		DrawBezierLine2(kek, RGBPIXEL::White());
	} catch (...) {
		return false;
	}
	return true;
}

void gfDrawScene()
{
    //gfClearScreen(RGBPIXEL::Black());
    //int x = gfGetMouseX(), y = gfGetMouseY();
    //gfDrawRectangle(x - 10, y - 10, x + 10, y + 10, RGBPIXEL::Green());
}

void gfCleanupScene()
{

}

void gfOnLMouseClick( int x, int y )
{

}

void gfOnRMouseClick( int x, int y )
{
}

void gfOnKeyDown( UINT key ) {

}

void gfOnKeyUp( UINT key )
{
}