oj.uz

Submission #253170

# Submission time Handle Problem Language Result Execution time Memory
253170 2020-07-27T09:20:35 Z Nightlight Wish (LMIO19_noras) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
#define point pair<long long, long long>
#define pii pair<int, bool>
using namespace std;

const long long limit = 2e8;

int N;
long long R;
long long a, b, c, d;
vector<pii> seg;

//a*x + b*y = c
//m = p/q


long long x_1, y_1, x_2, y_2, vx, vy;
long long p, q;
long double xx, yy;//terdekat

bool check(long long mid) {
  long long a = x_1 + mid * vx, b = y_1 + mid * vy;
  if(a > limit || a < -limit || b > limit || b < -limit) return 0;
  return a * a + b * b <= R * R;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin >> N >> R;
  long long l, r, res, mid;
  long long lb, ub;
  for(int i = 1; i <= N; i++) {
    cin >> x_1 >> y_1 >> x_2 >> y_2;
    if(x_1 == x_2) swap(x_1, y_1), swap(x_2, y_2);
    p = y_2 - y_1, q = x_2 - x_1;
    vx = q, vy = p;
//    cout << i << " " << p << " " << q << "\n";
    xx = (q * y_1 - p * x_1) * -p / (q * q + p * p);
    yy = (q * y_1 - p * x_1) * q / (q * q + p * p);
//    cout << xx << " " << yy << "\n";
    //kalau tedekat > R
    
    if(abs(q * y_1 - p * x_1) > R * R * sqrt(q * q + p * p)) continue;
    long long time = (xx - x_1) / q;
    //cari yang bawah dulu
    l = -limit, r = time, lb = -1;
    while(l <= r) {
      mid = (l + r) >> 1;
      if(check(mid)) {
        r = mid - 1;
        lb = mid;
      }else l = mid + 1;
    }
    l = time + 1, r = limit, ub = -1;
    while(l <= r) {
      mid = (l + r) >> 1;
      if(check(mid)) {
        l = mid + 1;
        ub = mid;
      }else r = mid - 1;
    }
    if(ub == -1 && lb == -1) continue;
    if(ub == -1) ub = time;
    if(lb == -1) lb = time + 1;
    seg.emplace_back(lb, 1);
    seg.emplace_back(ub + 1, 0);
  }
  sort(seg.begin(), seg.end());
  seg.emplace_back(limit, 1);
  //linesweep
  long long now;
  int cnt = 0, ans = 0;
  for(int i = 0; i < seg.size() - 1;) {
    now = seg[i].first;
    while(now == seg[i].first) {
      if(seg[i].second) cnt++;
      else cnt--;
      i++;
    }
    if(now >= 0) ans = max(ans, cnt);
  }
  cout << ans << "\n";
  cin >> N;
}

Compilation message

noras.cpp: In function 'int main()':
noras.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < seg.size() - 1;) {
                  ~~^~~~~~~~~~~~~~~~
noras.cpp:30:19: warning: unused variable 'res' [-Wunused-variable]
   long long l, r, res, mid;
                   ^~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -