oj.uz

Submission #299438

# Submission time Handle Problem Language Result Execution time Memory
299438 2020-09-14T22:32:14 Z Bruteforceman Wish (LMIO19_noras) C++11
0 / 100
 3 ms 384 KB 
#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 * i;
      }
    }
    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

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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -