fork(19) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <initializer_list>
  5.  
  6. struct point
  7. {
  8. 	double x, y;
  9. 	point(double x, double y) : x(x), y(y) {} // emplace_back() requires this constructor, at least, for g++ 4.5
  10. };
  11.  
  12. inline double square(double d)
  13. {
  14. 	return d*d;
  15. }
  16.  
  17. // Calculate coordinate(s) of crossing point(s) between 2 circles
  18. // (x-x1)^2 + (y-y1)^2 = r1^2 and (x-x2)^2 + (y-y2)^2 = r2^2 
  19. std::vector<point> cross_circle(double x1, double y1, double r1, double x2, double y2, double r2)
  20. {
  21. 	double la = 2 * (x1 - x2), lb = 2 * (y1 -y2), lc = r1*r1 - r2*r2 - x1*x1 + x2*x2 - y1*y1 + y2*y2;
  22. 	std::vector<point> result;
  23. 	if(la == 0) {
  24. 		if(lb == 0) {
  25. 			if(lc == 0) throw 1; // any point in whole plane can be root.
  26. 		} else {
  27. 			double Y = - lc / lb;
  28. 			double D = r1*r1 - (Y - y1)*(Y- y1);
  29. 			if(D > 0) {
  30. 				result.emplace_back(x1 + sqrt(D), Y);
  31. 				result.emplace_back(x1 - sqrt(D), Y);
  32. 			} else if(D == 0) {
  33. 				result.emplace_back(x1, Y);
  34. 			}
  35. 		}
  36. 	} else {
  37. 		double A = - lb / la, B = - lc / la;
  38. 		double D = square(2*A*(B-x1)-2*y1)-4*(A*A+1)*((B-x1)*(B-x1)+y1*y1-r1*r1);
  39. 		if(D > 0) {
  40. 			result.emplace_back(A*(-2*A*(B-x1)+2*y1+sqrt(D))/2/(1+A*A)+B, (-2*A*(B-x1)+2*y1+sqrt(D))/2/(1+A*A));
  41. 			result.emplace_back(A*(-2*A*(B-x1)+2*y1-sqrt(D))/2/(1+A*A)+B, (-2*A*(B-x1)+2*y1-sqrt(D))/2/(1+A*A));
  42. 		} else if(D == 0) {
  43. 			result.emplace_back(A*(-2*A*(B-x1)+2*y1)/2/(1+A*A)+B, (-2*A*(B-x1)+2*y1)/2/(1+A*A));
  44. 		}
  45. 	}
  46. 	return result;
  47. }
  48.  
  49. const double THRESHOLD = 0.000001;
  50.  
  51. inline double distance2(const point &p1, const point &p2)
  52. {
  53. 	return square(p1.x - p2.x) + square(p1.y - p2.y);
  54. }
  55.  
  56.  
  57. inline double distance(const point &p1, const point &p2)
  58. {
  59. 	return std::sqrt(distance2(p1, p2));
  60. }
  61.  
  62. inline bool near(const point& p1, const point &p2)
  63. {
  64. 	return distance2(p1, p2) <= square(THRESHOLD);
  65. }
  66.  
  67. bool check(int n, double dist, const std::vector<point> &v)
  68. {
  69. 	for(std::size_t i = 0; i != v.size(); ++i) {
  70. 		if(distance2({ 0, 0 }, v[i]) > 1 + THRESHOLD) return false; // Not in circle
  71. 		for(std::size_t j = i + 1; j < v.size(); ++j) {
  72. 			if(distance2(v[i], v[j]) + THRESHOLD < square(dist)) return false; // Distance unsatisfactory
  73. 		}
  74. 	}
  75. 	return true;
  76. }
  77.  
  78. bool process(int n, int level, double dist, std::vector<point> &v)
  79. {
  80. 	if(level == n) {
  81. 		return check(n, dist, v);
  82. 	} else if(level == 0) {
  83. 		v.clear();
  84. 		v.emplace_back(-1, 0);
  85. 		return process(n, level+1, dist, v);
  86. 	} else {
  87. 		std::vector<point> candidate;
  88. 		auto is_new = [&](const point &p)->bool {
  89. 			if(distance2({ 0, 0 }, p) > 1 + THRESHOLD) return false; // Not in circle
  90. 			for(int j = 0; j < level - 1; ++j) {
  91. 				if(near(p, v[j])) return false; // Duplicate
  92. 				if(distance2(p, v[j]) + THRESHOLD < square(dist)) return false; // Distance unsatisfactory
  93. 			}
  94. 			for(std::size_t j = 0; j != candidate.size(); ++j) {
  95. 				if(near(p, candidate[j])) return false; // Duplicate in candidates
  96. 			}
  97. 			return true;
  98. 		};
  99. 		try {
  100. 			auto v1 = cross_circle(0, 0, 1, v[level-1].x, v[level-1].y, dist);
  101. 			if(v1.size() > 1 && level == 1) v1.pop_back(); // vertically symmetric
  102. 			for(std::size_t i = 0; i != v1.size(); ++i) {
  103. 				if(is_new(v1[i])) candidate.push_back(v1[i]);
  104. 			}
  105. 		} catch(int) {
  106. 			// When v[level-1].x == v[level-1].y == 0 && dist == 1, exception thrown
  107. 			// We can simply ignore because candidates are selected by the below criteria
  108. 		}
  109. 		for(int i = 0; i < level - 1; ++i) {
  110. 			auto v2 = cross_circle(v[i].x, v[i].y, dist, v[level-1].x, v[level-1].y, dist);
  111. 			for(std::size_t j = 0; j != v2.size(); ++j) {
  112. 				if(is_new(v2[j])) candidate.push_back(v2[j]);
  113. 			}
  114. 		}
  115. 		for(std::size_t i = 0; i != candidate.size(); ++i) {
  116. 			v.push_back(candidate[i]);
  117. 			if(process(n, level+1, dist, v)) return true;
  118. 			v.pop_back();
  119. 		}
  120. 		return false;
  121. 	}
  122. }
  123.  
  124. int main(void)
  125. {
  126. 	int n; std::cin >> n;
  127. 	std::vector<point> result;
  128. 	double l = THRESHOLD, r = 2.1, t;
  129. 	for(int i=0;i<30;++i) {
  130. 		t = (l+r)/2;
  131. 		if(process(n, 0, t, result)) {
  132. 			l = t;
  133. 		} else {
  134. 			r = t;
  135. 		}
  136. 	}
  137. 	if(process(n, 0, l, result)) {
  138. 		std::cout << "POSSIBLE: " << l << std::endl;
  139. 		for(std::size_t i = 0; i != result.size(); ++i) {
  140. 			std::cout << result[i].x << ',' << result[i].y << std::endl;
  141. 		}
  142. 	} else {
  143. 		std::cout << "IMPOSSIBLE" << std::endl;
  144. 	}
  145. 	return 0;
  146. }
  147.  
Success #stdin #stdout 7.67s 3028KB
comments (?)
stdin
copy 
21
stdout
copy 
POSSIBLE: 0.470009
-1,0
-0.889546,0.456846
-0.582583,0.812771
-0.146923,0.989148
0.321194,0.947014
0.718356,0.695676
0.956827,0.290657
0.983927,-0.17857
0.793669,-0.608349
0.516598,-0.228691
0.489498,0.240536
0.115059,0.524619
-0.340705,0.409778
-0.530427,-0.0202381
-0.78274,-0.416781
-0.313167,-0.43702
-0.485138,-0.874437
-0.0320695,-0.999486
0.428084,-0.903739
0.151012,-0.524082
0.0779898,-0.0597796
https://ideone.com/fOz4R
language:
C++14 (gcc 8.3)
created:
12 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!