Submission #715955

#	Time	Username	Problem	Language	Result	Execution time	Memory
715955		tengiz05	Wish (LMIO19_noras)	C++17	38 / 100	1062 ms	5696 KiB

noras

#include <bits/stdc++.h>

using i64 = long long;

struct Vector {
    i64 x, y;
    Vector(i64 x = 0, i64 y = 0) : x(x), y(y) {}
    Vector operator-(Vector b) {
        return Vector(x - b.x, y - b.y);
    }
    Vector operator+(Vector b) {
        return Vector(x + b.x, y + b.y);
    }
    i64 length() {
        return x * x + y * y;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    i64 R;
    std::cin >> n >> R;
    
    std::vector<Vector> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
    }
    
    std::vector<std::pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        int l = -1, r = -1;
        Vector cur = a[i];
        Vector delta = b[i] - a[i];
        for (int j = 0; j < 20005; j++) {
            if (cur.length() <= R * R) {
                if (l == -1) {
                    l = j;
                }
                r = j;
            }
            cur = cur + delta;
        }
        if (l != -1) {
            v.push_back({l, r});
        }
    }
    
    std::vector<int> cnt(20005);
    for (auto [l, r] : v) {
        for (int i = l; i <= r; i++) {
            cnt[i]++;
        }
    }
    
    std::cout << *max_element(cnt.begin(), cnt.end()) << "\n";
    
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 23
• Subtask 3: 15 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7