Advertisement
Guest User

Untitled

a guest
Nov 25th, 2015
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <map>
  7.  
  8. #define eps 1e-8
  9. #define INF 1000000
  10. #define PI 3.14159265359
  11.  
  12. using namespace std;
  13.  
  14. struct point
  15. {
  16. double x, y;
  17.  
  18. point(double x = 0, double y = 0) :x(x), y(y) {}
  19. };
  20.  
  21. bool operator == (const point& a, const point& b)
  22. {
  23. return fabs(a.x - b.x) < eps && fabs(a.y - b.y) < eps;
  24. }
  25.  
  26. bool operator != (const point& a, const point& b)
  27. {
  28. return !(a == b);
  29. }
  30.  
  31. bool operator < (const point& a, const point& b)
  32. {
  33. return (a.x + eps < b.x) || (fabs(a.x - b.x) < eps && (a.y + eps < b.y));
  34. }
  35.  
  36. point operator-(point a, point b)
  37. {
  38. return point(a.x - b.x, a.y - b.y);
  39. }
  40.  
  41. point operator+(point a, point b)
  42. {
  43. return point(a.x + b.x, a.y + b.y);
  44. }
  45.  
  46. point operator*(point a, double k)
  47. {
  48. return point(a.x*k, a.y*k);
  49. }
  50.  
  51. point operator/(point a, double k)
  52. {
  53. return point(a.x / k, a.y / k);
  54. }
  55.  
  56. double dist2(point a, point b = point(0, 0))
  57. {
  58. point c = (a - b);
  59. return (c.x*c.x) + (c.y*c.y);
  60. }
  61.  
  62. double dist(point a, point b = point(0, 0))
  63. {
  64. return sqrt(dist2(a, b));
  65. }
  66.  
  67. point perp(point a)
  68. {
  69. return point(a.y, -a.x);
  70. }
  71.  
  72. point norm(point p)
  73. {
  74. return p / dist(p);
  75. }
  76.  
  77. double dot(point a, point b)
  78. {
  79. return a.x*b.x + a.y*b.y;
  80. }
  81.  
  82. struct Edge
  83. {
  84. point a, b;
  85. double w;
  86.  
  87. Edge(point a, point b, double w) :a(a), b(b), w(w) {}
  88. };
  89.  
  90.  
  91. point intersect_circle_circle(point o, double r, point O, double R, bool up = true)
  92. {
  93. double d = dist(o, O)/2.0;
  94. double h = sqrt(R*R-d*d);
  95.  
  96. point H = (o+O)/2.0;
  97. if (up)
  98. {
  99. point p = perp(norm(O - o))*h;
  100. point a = (O - o);
  101. a = norm(a);
  102. a = perp(a);
  103. a = a*h;
  104. return H + a;
  105. }
  106. else
  107. {
  108. point p = perp(norm(O - o))*h;
  109. point a = (O - o);
  110. a = norm(a);
  111. a = perp(a);
  112. a = a*h;
  113. return H - a;
  114. }
  115. }
  116.  
  117. bool point_in_circle(point p, point O, double r)
  118. {
  119. return dist2(p, O)-eps <= r*r;
  120. }
  121.  
  122. double r;
  123.  
  124. vector<point> get_all_points(const vector<point>& v, double t)
  125. {
  126. vector<point> p;
  127. for (int i = 0; i < v.size(); i++)
  128. for (int j = i+1; j < v.size(); j++)
  129. if (v[i] != v[j])
  130. {
  131. p.push_back(intersect_circle_circle(v[i], t, v[j], t));
  132. p.push_back(intersect_circle_circle(v[i], t, v[j], t, false));
  133. }
  134.  
  135. return p;
  136. }
  137.  
  138. bool exist_intersect_circle_circle(point o, double r, point O, double R)
  139. {
  140. return (r + R >= dist2(o, O)) && (dist(o, O) + r >= R) && (dist(o, O) + R >= r);
  141. }
  142.  
  143. int count_of_intersections(point O, const vector<point>& v, double t)
  144. {
  145. int k = 0;
  146. for (int i = 0; i < v.size(); i++)
  147. k += point_in_circle(O, v[i], t);
  148. return k;
  149. }
  150.  
  151. bool check(const vector<point>& v, double t)
  152. {
  153. vector<point> p = get_all_points(v, t);
  154. for (int i = 0; i < p.size(); i++)
  155. {
  156. if (count_of_intersections(p[i], v, t) < 3 && point_in_circle(p[i], point(0, 0), r))
  157. return false;
  158. }
  159. return true;
  160. }
  161.  
  162. int main()
  163. {
  164. int n;
  165. cin >> n >> r;
  166. vector<point> v(n);
  167. for (int i = 0; i < n; i++)
  168. {
  169. cin >> v[i].x >> v[i].y;
  170. }
  171.  
  172. sort(v.begin(), v.end());
  173. v.erase(unique(v.begin(), v.end()), v.end());
  174.  
  175. double left = 0, right = 4*r + 1.0;
  176.  
  177. while (right - left > eps)
  178. {
  179.  
  180. double t = (left + right) / 2;
  181.  
  182. if (check(v, t))
  183. right = t;
  184. else
  185. left = t;
  186. }
  187.  
  188. cout << fixed << setprecision(8) << left << endl;
  189. //cout << fixed << setprecision(3) << ans.x << " " << fixed << setprecision(3) << ans.y;
  190.  
  191. return 0;
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement