Submission #299439

#	Time	Username	Problem	Language	Result	Execution time	Memory
299439		Bruteforceman	Wish (LMIO19_noras)	C++11	100 / 100	558 ms	9216 KiB

noras

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const long long inf = 1e16;
typedef long long dtype;
struct point {
  dtype x, y;
  point (dtype x, dtype y) : x(x), y(y) {}
  point () {}
  point operator - (point p) const {
    return point(x - p.x, y - p.y);
  }
  point operator + (point p) const {
    return point(x + p.x, y + p.y);
  }
  point operator * (dtype val) const {
    return point(x * val, y * val);
  }
};
dtype dot(point p, point q) {
  return p.x * q.x + p.y * q.y;
}
int main() {
  int n, R;
  cin >> n >> R;
  map <long long, int> cnt;
  for(int i = 0; i < n; i++) {
    int a, b;
    int c, d;
    cin >> a >> b >> c >> d;
    point p (a, b);
    point q (c, d);
    long long u = dot(point(0, 0) - p, q - p) / dot(q - p, q - p);
    long long piv = LLONG_MAX;
    for(int x = -1; x <= 1; x++) {
      point r = p + ((q - p) * (u + x));
      if(dot(r, r) <= 1LL * R * R) {
        piv = u + x;
        break;
      }
    }
    if(piv == LLONG_MAX) continue;
    long long from, to;
    for(int dir : {-1, 1}) {
      long long l = 0, r = 2 * R + 1;
      while(l < r) {
        long long mid = (l + r + 1) >> 1;
        point f = p + ((q - p) * (piv + dir * mid));
        if(abs(f.x) <= R && abs(f.y) <= R && dot(f, f) <= 1LL * R * R) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      if(dir == -1) {
        from = piv + dir * l;
        from = max(0LL, from);
      } else {
        to = piv + dir * l;
      }
    }
    if(from <= to) {
      cnt[from] += 1;
      cnt[to + 1] -= 1; 
     // cout << from << " " << to << endl;
    }
  }
  int sum = 0;
  int ans = 0;
  for(auto i : cnt) {
    sum += i.second;
    ans = max(ans, sum);
  }
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:64:14: warning: 'to' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |       cnt[to + 1] -= 1;
      |           ~~~^~~

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