fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <algorithm>
  5. #include <tuple>
  6. #include <random>
  7. #include <chrono>
  8. #include <cstdint>
  9.  
  10. typedef std::vector<std::size_t> DType;
  11. static const std::size_t DisX = 16;
  12. static const std::size_t DisY = 16;
  13.  
  14. typedef std::tuple<std::size_t,double,double,double, double, double, double> Line;//idx,x1,y1,x2,y2,a,b;
  15. typedef std::vector<Line> LType;
  16.  
  17. typedef std::vector<std::set<std::size_t>> GType;
  18. typedef std::pair<std::uint64_t, GType> RType;
  19.  
  20.  
  21. DType MakeDataRev(std::size_t N){
  22. 	DType vec(N);
  23. 	std::size_t i = 0;
  24.  
  25. 	for (auto& o : vec)o = i++;
  26.  
  27. 	std::reverse(vec.begin(), vec.end());
  28.  
  29. 	return vec;
  30. }
  31. DType MakeDataRnd(std::size_t N){
  32. 	DType vec(N);
  33. 	std::size_t i = 0;
  34.  
  35. 	std::random_device rd;
  36. 	std::mt19937 mt(rd());
  37.  
  38.  
  39. 	for (auto& o : vec)o = i++;
  40.  
  41. 	std::shuffle(vec.begin(), vec.end(),mt);
  42.  
  43. 	return vec;
  44. }
  45. LType MakeLines(DType& vec){
  46. 	LType R;
  47. 	double X1 = 0;
  48. 	double Y1 = 0;
  49. 	double X2 = 0;
  50. 	double Y2 = 0;
  51. 	double A = 0;
  52. 	double B = 0;
  53.  
  54. 	for (std::size_t i = 0; i < vec.size(); i++){
  55. 		X1 = vec[i] * DisX;
  56. 		Y1 = DisY;
  57. 		X2 = i*DisX;
  58. 		Y2 = 0;
  59. 		A = 0;
  60. 		if((X1-X2) != 0)A = (Y1 - Y2) / (X1 - X2);
  61.  
  62. 		B = Y1-(A*X1);
  63. 		R.push_back(std::make_tuple(i,X1, Y1, X2, Y2, A, B));
  64. 	}
  65.  
  66. 	return R;
  67. }
  68.  
  69. bool IsCross(Line& A, Line& B){
  70. 	double AA = (std::get<5>(A)-std::get<5>(B));
  71. 	double BB = (std::get<6>(B)-std::get<6>(A));
  72.  
  73. 	double X =0;
  74. 	if (AA != 0) X = BB / AA;
  75. 	double Y = std::get<5>(A)*X + std::get<6>(A);
  76.  
  77. 	return (Y >= 0 && Y <= DisY)&&(X!=0);
  78. 	//return X!=0;
  79. }
  80.  
  81. RType MakeHoge(DType& vec){
  82. 	GType R(vec.size());
  83.  
  84. 	auto ML = MakeLines(vec);
  85.  
  86. 	std::uint64_t count = 0;
  87.  
  88. 	for (size_t i = 0; i <ML.size() ; i++){
  89. 		for (size_t j = i+1; j < ML.size(); j++)
  90. 		{
  91. 			//if (R[i].find(j) != R[i].end()) continue;
  92. 			if (IsCross(ML[i], ML[j]) == true){
  93. 			//	R[std::get<0>(ML[i])].insert(std::get<0>(ML[j]));
  94. 			//	R[std::get<0>(ML[j])].insert(std::get<0>(ML[i]));
  95. 				count++;
  96. 			}
  97.  
  98. 		}
  99. 	}
  100.  
  101. 	return std::make_pair(count,R);
  102.  
  103.  
  104. }
  105.  
  106. RType TimeCount(std::size_t N, bool IsRandom = false){
  107. 	DType D;
  108. 	auto ST = std::chrono::high_resolution_clock::now();
  109.  
  110. 	if (IsRandom == false){
  111. 		D = MakeDataRev(N);
  112. 	}
  113. 	else{
  114. 		D = MakeDataRnd(N);
  115. 	}
  116.  
  117. 	auto C = MakeHoge(D);
  118. 	auto EN = std::chrono::high_resolution_clock::now();
  119. 	auto El = std::chrono::duration_cast<std::chrono::milliseconds>(EN - ST);
  120. 	std::cout << "Try "<<N<<" Line To Cross The " << C.first << " Count!!"<<std::endl;
  121. 	std::cout << "Time Using At " << El.count() << "ms!!"<<std::endl;
  122.  
  123. 	return C;
  124. }
  125.  
  126. int main(){
  127.  
  128. 	TimeCount(10240);
  129. 	TimeCount(10240,true);
  130.  
  131. 	return 0;
  132. }
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
Success #stdin #stdout 2.54s 3956KB
comments (?)
stdin 
Standard input is empty
stdout 
Try 10240 Line To Cross The 52423680 Count!!
Time Using At 1090ms!!
Try 10240 Line To Cross The 26334977 Count!!
Time Using At 1455ms!!
https://ideone.com/cqKPGU
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!