#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <tuple>
#include <random>
#include <chrono>
#include <cstdint>

typedef std::vector<std::size_t> DType;
static const std::size_t DisX = 16;
static const std::size_t DisY = 16;

typedef std::tuple<std::size_t,double,double,double, double, double, double> Line;//idx,x1,y1,x2,y2,a,b;
typedef std::vector<Line> LType;

typedef std::vector<std::set<std::size_t>> GType;
typedef std::pair<std::uint64_t, GType> RType;


DType MakeDataRev(std::size_t N){
	DType vec(N);
	std::size_t i = 0;

	for (auto& o : vec)o = i++;

	std::reverse(vec.begin(), vec.end());

	return vec;
}
DType MakeDataRnd(std::size_t N){
	DType vec(N);
	std::size_t i = 0;

	std::random_device rd;
	std::mt19937 mt(rd());


	for (auto& o : vec)o = i++;

	std::shuffle(vec.begin(), vec.end(),mt);

	return vec;
}
LType MakeLines(DType& vec){
	LType R;
	double X1 = 0;
	double Y1 = 0;
	double X2 = 0;
	double Y2 = 0;
	double A = 0;
	double B = 0;

	for (std::size_t i = 0; i < vec.size(); i++){
		X1 = vec[i] * DisX;
		Y1 = DisY;
		X2 = i*DisX;
		Y2 = 0;
		A = 0;
		if((X1-X2) != 0)A = (Y1 - Y2) / (X1 - X2);

		B = Y1-(A*X1);
		R.push_back(std::make_tuple(i,X1, Y1, X2, Y2, A, B));
	}

	return R;
}

bool IsCross(Line& A, Line& B){
	double AA = (std::get<5>(A)-std::get<5>(B));
	double BB = (std::get<6>(B)-std::get<6>(A));

	double X =0;
	if (AA != 0) X = BB / AA;
	double Y = std::get<5>(A)*X + std::get<6>(A);

	return (Y >= 0 && Y <= DisY)&&(X!=0);
	//return X!=0;
}

RType MakeHoge(DType& vec){
	GType R(vec.size());

	auto ML = MakeLines(vec);

	std::uint64_t count = 0;

	for (size_t i = 0; i <ML.size() ; i++){
		for (size_t j = i+1; j < ML.size(); j++)
		{
			//if (R[i].find(j) != R[i].end()) continue;
			if (IsCross(ML[i], ML[j]) == true){
			//	R[std::get<0>(ML[i])].insert(std::get<0>(ML[j]));
			//	R[std::get<0>(ML[j])].insert(std::get<0>(ML[i]));
				count++;
			}

		}
	}

	return std::make_pair(count,R);


}

RType TimeCount(std::size_t N, bool IsRandom = false){
	DType D;
	auto ST = std::chrono::high_resolution_clock::now();
	
	if (IsRandom == false){
		D = MakeDataRev(N);
	}
	else{
		D = MakeDataRnd(N);
	}

	auto C = MakeHoge(D);
	auto EN = std::chrono::high_resolution_clock::now();
	auto El = std::chrono::duration_cast<std::chrono::milliseconds>(EN - ST);
	std::cout << "Try "<<N<<" Line To Cross The " << C.first << " Count!!"<<std::endl;
	std::cout << "Time Using At " << El.count() << "ms!!"<<std::endl;

	return C;
}

int main(){
	
	TimeCount(10240);
	TimeCount(10240,true);

	return 0;
}