Submission #253170

#	Time	Username	Problem	Language	Result	Execution time	Memory
253170		Nightlight	Wish (LMIO19_noras)	C++14	0 / 100	1 ms	384 KiB

noras

#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 (stderr)

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
• Subtask 2: 0 / 23
• Subtask 3: 0 / 15
• Subtask 4: 0 / 32
• Subtask 5: 0 / 7