Advertisement
bibaboba12345

slonopotam

Oct 4th, 2021
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <random>
  7. #include <set>
  8. #include <iomanip>
  9. using namespace std;
  10. const int N = 5e5 + 7;
  11. const long long INF = -1;
  12. const long double eps = 1e-9;
  13. struct vect {
  14. long double x, y;
  15. };
  16.  
  17. vect operator+(vect a, vect b)
  18. {
  19. return { a.x + b.x, a.y + b.y };
  20. }
  21. vect operator-(vect& a, vect& b)
  22. {
  23. return { a.x - b.x, a.y - b.y };
  24. }
  25. vect operator*(vect& a, long double x)
  26. {
  27. return { a.x * x, a.y * x };
  28. }
  29. vect operator/(vect& a, long double x)
  30. {
  31. return { a.x / x, a.y / x };
  32. }
  33.  
  34. long double operator %(const vect& a, const vect& b) { // vect
  35. return a.x * b.y - a.y * b.x;
  36. }
  37.  
  38. long double operator *(const vect& a, const vect& b) { // skal
  39. return a.x * b.x + a.y * b.y;
  40. }
  41.  
  42. bool operator==(vect& a, vect& b)
  43. {
  44. return abs(a.x - b.x) < eps && abs(b.y - a.y) < eps;
  45. }
  46. long double len(vect a)
  47. {
  48. return sqrtl(a.x * a.x + a.y * a.y);
  49. }
  50. vect norm(vect a, long double x)
  51. {
  52. long double l = len(a);
  53. a = a / l;
  54. a = a * x;
  55. return a;
  56. }
  57. vect perp(vect a)
  58. {
  59. return { a.y * -1, a.x };
  60. }
  61. vector<vect> PerOkr(vect o1, long double r1, vect o2, long double r2)
  62. {
  63. vector<vect> ans;
  64. ans.clear();
  65. vect o2o1 = o1 - o2;
  66. long double z = len(o2o1);
  67. if (abs(r1 - r2) < eps && o1 == o2) {
  68. ans.push_back({ 1, 1 });
  69. ans.push_back({ 2, 2 });
  70. ans.push_back({ 3, 3 });
  71. return ans;
  72. }
  73. if (abs(z - r1 - r2) < eps) {
  74. ans.push_back(o2 + norm(o2o1, r2));
  75. return ans;
  76. }
  77. if (z > r1 + r2 + eps) { //
  78. return ans;
  79. }
  80. if (abs(z + r1 - r2) < eps) { // z == r1+r2, vnutr kas
  81. ans.push_back(o2 + norm(o2o1, r2));
  82. return ans;
  83. }
  84. if (abs(z + r2 - r1) < eps) { // z + r2 == r1, vnutr kas
  85. ans.push_back(o1 + norm(o2o1 * -1, r1));
  86. return ans;
  87. }
  88. if (z + r2 < r1 + eps || z + r1 < r2 + eps) { // odin vnutri drugogo
  89. return ans;
  90. }
  91. long double x = (z - (r1 * r1 - r2 * r2) / z) / 2;
  92. long double y = sqrtl(r2 * r2 - x * x);
  93. vect h = o2 + norm(o2o1, x);
  94. vect per = norm(perp(o2o1), y);
  95. cout << fixed << setprecision(10);
  96. vect o1h = h - o1;
  97. ans.push_back(h + per);
  98. ans.push_back(h - per);
  99. return ans;
  100. }
  101.  
  102. vector<vect> Kas(vect o1, long double r1, vect o2) {
  103. vector<vect> ans;
  104. vect o2o1 = o1 - o2;
  105. long double z = len(o2o1);
  106. if (z < r1 - eps) {
  107. return ans;
  108. }
  109. if (abs(z - r1) < eps) {
  110. ans.push_back(o2);
  111. return ans;
  112. }
  113. long double r2 = sqrtl(z * z - r1 * r1);
  114. return PerOkr(o1, r1, o2, r2);
  115. }
  116.  
  117. vect Intersect(vect a, vect b, vect c, vect d) {
  118. long double a1 = b.y - a.y;
  119. long double b1 = a.x - b.x;
  120. long double c1 = -1 * (a1 * a.x + b1 * a.y);
  121. long double a2 = d.y - c.y;
  122. long double b2 = c.x - d.x;
  123. long double c2 = -1 * (a1 * c.x + b1 * c.y);
  124. long double D = a1 * b2 - a2 * b1;
  125. long double Dx = c1 * b2 - c2 * b1;
  126. long double Dy = a1 * c2 - a2 * c1;
  127. if (D == 0) {
  128. return { -1337, -1448 };
  129. }
  130. return { -1 * (Dx / D), -1 * (Dy / D) };
  131. }
  132.  
  133. long double RasstDoOtr(vect a, vect b, vect c) {
  134. vect ca = a - c;
  135. vect cb = b - c;
  136. vect bc = c - b;
  137. vect ba = a - b;
  138. vect ac = c - a;
  139. vect ab = b - a;
  140. if (ab * ac <= 0 || ba * bc <= 0) {
  141. return min(len(ac), len(bc));
  142. }
  143. return abs((ca % cb) / len(ab));
  144. }
  145.  
  146. bool intC(vect o, long double r, vect a, vect b) {
  147. return RasstDoOtr(a, b, o) <= r + eps;
  148. }
  149. vect o, v, k;
  150. long double r1, r2, n, ans;
  151. vector<vect> ans1, ans2;
  152. int main()
  153. {
  154. cin >> v.x >> v.y >> k.x >> k.y >> o.x >> o.y >> r1;
  155. cout << fixed << setprecision(10);
  156. if (!intC(o, r1, v, k)) {
  157. cout << len(k - v);
  158. return 0;
  159. }
  160. ans1 = Kas(o, r1, v);
  161. ans2 = Kas(o, r1, k);
  162. ans = 1e12;
  163. for (int i = 0; i < ans1.size(); i++) {
  164. for (int j = 0; j < ans2.size(); j++) {
  165. vect oi = ans1[i] - o;
  166. vect oj = ans2[j] - o;
  167. //long double sect = min(abs(atan2(oi % oj, oi * oj)) * r1, 2 * acos(-1) * r1 - abs(atan2(oi % oj, oi * oj)) * r1);
  168. long double sect = abs(atan2(oi % oj, oi * oj)) * r1;
  169. ans = min(ans, len(v - ans1[i]) + len(k - ans2[j]) + sect);
  170. }
  171. }
  172. cout << ans;
  173. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement