Advertisement
TrickmanOff

taskkkkkk

Nov 5th, 2020
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.64 KB | None | 0 0
  1. //#pragma optimization_level 3
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  3. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <fstream>
  7. #include <vector>
  8. #include <queue>
  9. #include <functional>
  10. #include <set>
  11. #include <map>
  12. #include <math.h>
  13. #include <cmath>
  14. #include <string>
  15. //#include <random>
  16. //#include <unordered_set>
  17. //#include <unordered_map>
  18. #include <bitset>
  19. #include <string.h>
  20. #include <stack>
  21. #include <assert.h>
  22. #include <list>
  23. #include <time.h>
  24. //#include <tuple>
  25. #include <memory>
  26. //#include <chrono>
  27. using namespace std;
  28. //
  29. #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
  30. //#define cin in
  31. //#define cout out
  32. #define ll long long
  33. #define db double
  34. #define ld long double
  35. #define uset unordered_set
  36. #define umap unordered_map
  37. #define ms multiset
  38. #define pb push_back
  39. //#define pq priority_queue
  40. #define umap unordered_map
  41. #define uset unordered_set
  42. #define ull unsigned long long
  43. #define pii pair<int, int>
  44. #define pll pair<ll, ll>
  45. #define pdd pair<ld, ld>
  46. #define pnn pair<Node*, Node*>
  47. #define uid uniform_int_distribution
  48. #define PI acos(-1.0)
  49. //#define sort(a, b) sort(a.begin(), a.end(), b())
  50. //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  51. ifstream in("input.txt");
  52. ofstream out("output.txt");
  53.  
  54. int n;
  55. ld R;
  56.  
  57. struct Pnt {
  58. ld x, y;
  59. };
  60.  
  61. struct Circ {
  62. Pnt cent;
  63. ld r;
  64. };
  65.  
  66. vector<Circ> trees;
  67. vector<ld> inter_y;
  68.  
  69. ld dist(Pnt a, Pnt b) {
  70. return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
  71. }
  72.  
  73. void calc_inter() {
  74. for (auto& [cent, r] : trees) {
  75. inter_y.push_back(cent.y - r);
  76. inter_y.push_back({cent.y + r});
  77. }
  78.  
  79. for (int i = 0; i < n; ++i) {
  80. for (int j = i + 1; j < n; ++j) {
  81. // начало координат - центр первой
  82. ld r1 = trees[i].r;
  83. ld r2 = trees[j].r;
  84. ld x1 = trees[i].cent.x;
  85. ld y1 = trees[i].cent.y;
  86. ld x2 = trees[j].cent.x - x1;
  87. ld y2 = trees[j].cent.y - y1;
  88. // не пересекаются
  89. if (dist({0, 0}, {x2, y2}) > r1 + r2) continue;
  90.  
  91. ld a = -2 * x2;
  92. ld b = -2 * y2;
  93. ld c = r2 * r2 - r1 * r1 - x2 * x2 - y2 * y2;
  94.  
  95. if (a == 0) {
  96. ld y = c / b;
  97. ld x = sqrt(r1 * r1 - y * y);
  98. inter_y.push_back(y + y1);
  99. } else {
  100. ld A = a * a + b * b;
  101. ld B = -2 * b * c;
  102. ld C = c*c - a * a * r1 * r1;
  103.  
  104. ld D = B * B - 4 * A * C;
  105.  
  106. ld y = (-B + sqrt(D)) / (2 * A);
  107. ld x = (c - b * y) / a;
  108. inter_y.push_back(y + y1);
  109. if (D != 0) {
  110. ld y = (-B - sqrt(D)) / (2 * A);
  111. ld x = (c - b * y) / a;
  112. inter_y.push_back(y + y1);
  113. }
  114. }
  115. }
  116. }
  117. }
  118.  
  119. void input() {
  120. cin >> n >> R;
  121. trees.resize(n);
  122. for (auto& c : trees)
  123. cin >> c.cent.x >> c.cent.y >> c.r;
  124. }
  125.  
  126. struct C{
  127. ld x;
  128. int num;
  129. };
  130.  
  131. Pnt ans_p;
  132. int ans_cnt = 0;
  133.  
  134. void solve(ld y) {
  135. vector<C> vec;
  136. for (int i = 0; i < n; ++i) {
  137. auto& cent = trees[i].cent;
  138. ld r = trees[i].r;
  139.  
  140. ld x1 = cent.x, y1 = cent.y;
  141. if (y > y1 + r || y < y1 - r) continue;
  142. ld a = 1;
  143. ld b = -2*x1;
  144. ld c = x1 * x1 + (y - y1) * (y - y1) - r * r;
  145. ld d = b*b - 4*a*c;
  146.  
  147. ld xx = (-b - sqrt(d)) / (2 * a);
  148. vec.push_back({xx, -1});
  149. if (d != 0) {
  150. xx = (-b + sqrt(d)) / (2 * a);
  151. vec.push_back({xx, 1});
  152. }
  153. }
  154. sort(vec.begin(), vec.end(), [](const C& a, const C&b) {return a.x < b.x;});
  155. vector<int> pnts(n, 0);
  156.  
  157. int lp = 0;
  158. int rp = 0;
  159. int cnt = 0;
  160.  
  161. while (rp < vec.size()) {
  162. // берём открывающиеся
  163. ld x = vec[rp].x;
  164. while (rp < vec.size() && vec[rp].x == x) {
  165. if (pnts[vec[rp].num]++ == 0) ++cnt;
  166. ++rp;
  167. };
  168.  
  169. while (x - vec[lp].x > R) {
  170. if (--pnts[vec[lp].num] == 0) --cnt;
  171. ++lp;
  172. }
  173.  
  174. if (cnt > ans_cnt) {
  175. ans_cnt = cnt;
  176. ans_p = {(vec[rp-1].x - vec[lp].x) / 2, y};
  177. }
  178. }
  179. }
  180.  
  181. int main() {
  182. input();
  183.  
  184. calc_inter();
  185. sort(inter_y.begin(), inter_y.end());
  186.  
  187. for (ld y : inter_y) {
  188. solve(y);
  189. }
  190.  
  191. int ttk = 0;
  192. }
  193.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement