Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma optimization_level 3
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <functional>
- #include <set>
- #include <map>
- #include <math.h>
- #include <cmath>
- #include <string>
- //#include <random>
- //#include <unordered_set>
- //#include <unordered_map>
- #include <bitset>
- #include <string.h>
- #include <stack>
- #include <assert.h>
- #include <list>
- #include <time.h>
- //#include <tuple>
- #include <memory>
- //#include <chrono>
- using namespace std;
- //
- #define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
- //#define cin in
- //#define cout out
- #define ll long long
- #define db double
- #define ld long double
- #define uset unordered_set
- #define umap unordered_map
- #define ms multiset
- #define pb push_back
- //#define pq priority_queue
- #define umap unordered_map
- #define uset unordered_set
- #define ull unsigned long long
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pdd pair<ld, ld>
- #define pnn pair<Node*, Node*>
- #define uid uniform_int_distribution
- #define PI acos(-1.0)
- //#define sort(a, b) sort(a.begin(), a.end(), b())
- //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
- ifstream in("input.txt");
- ofstream out("output.txt");
- int n;
- ld R;
- struct Pnt {
- ld x, y;
- };
- struct Circ {
- Pnt cent;
- ld r;
- };
- vector<Circ> trees;
- vector<ld> inter_y;
- ld dist(Pnt a, Pnt b) {
- return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
- }
- void calc_inter() {
- for (auto& [cent, r] : trees) {
- inter_y.push_back(cent.y - r);
- inter_y.push_back({cent.y + r});
- }
- for (int i = 0; i < n; ++i) {
- for (int j = i + 1; j < n; ++j) {
- // начало координат - центр первой
- ld r1 = trees[i].r;
- ld r2 = trees[j].r;
- ld x1 = trees[i].cent.x;
- ld y1 = trees[i].cent.y;
- ld x2 = trees[j].cent.x - x1;
- ld y2 = trees[j].cent.y - y1;
- // не пересекаются
- if (dist({0, 0}, {x2, y2}) > r1 + r2) continue;
- ld a = -2 * x2;
- ld b = -2 * y2;
- ld c = r2 * r2 - r1 * r1 - x2 * x2 - y2 * y2;
- if (a == 0) {
- ld y = c / b;
- ld x = sqrt(r1 * r1 - y * y);
- inter_y.push_back(y + y1);
- } else {
- ld A = a * a + b * b;
- ld B = -2 * b * c;
- ld C = c*c - a * a * r1 * r1;
- ld D = B * B - 4 * A * C;
- ld y = (-B + sqrt(D)) / (2 * A);
- ld x = (c - b * y) / a;
- inter_y.push_back(y + y1);
- if (D != 0) {
- ld y = (-B - sqrt(D)) / (2 * A);
- ld x = (c - b * y) / a;
- inter_y.push_back(y + y1);
- }
- }
- }
- }
- }
- void input() {
- cin >> n >> R;
- trees.resize(n);
- for (auto& c : trees)
- cin >> c.cent.x >> c.cent.y >> c.r;
- }
- struct C{
- ld x;
- int num;
- };
- Pnt ans_p;
- int ans_cnt = 0;
- void solve(ld y) {
- vector<C> vec;
- for (int i = 0; i < n; ++i) {
- auto& cent = trees[i].cent;
- ld r = trees[i].r;
- ld x1 = cent.x, y1 = cent.y;
- if (y > y1 + r || y < y1 - r) continue;
- ld a = 1;
- ld b = -2*x1;
- ld c = x1 * x1 + (y - y1) * (y - y1) - r * r;
- ld d = b*b - 4*a*c;
- ld xx = (-b - sqrt(d)) / (2 * a);
- vec.push_back({xx, -1});
- if (d != 0) {
- xx = (-b + sqrt(d)) / (2 * a);
- vec.push_back({xx, 1});
- }
- }
- sort(vec.begin(), vec.end(), [](const C& a, const C&b) {return a.x < b.x;});
- vector<int> pnts(n, 0);
- int lp = 0;
- int rp = 0;
- int cnt = 0;
- while (rp < vec.size()) {
- // берём открывающиеся
- ld x = vec[rp].x;
- while (rp < vec.size() && vec[rp].x == x) {
- if (pnts[vec[rp].num]++ == 0) ++cnt;
- ++rp;
- };
- while (x - vec[lp].x > R) {
- if (--pnts[vec[lp].num] == 0) --cnt;
- ++lp;
- }
- if (cnt > ans_cnt) {
- ans_cnt = cnt;
- ans_p = {(vec[rp-1].x - vec[lp].x) / 2, y};
- }
- }
- }
- int main() {
- input();
- calc_inter();
- sort(inter_y.begin(), inter_y.end());
- for (ld y : inter_y) {
- solve(y);
- }
- int ttk = 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement