Submission #253171

#	Time	Username	Problem	Language	Result	Execution time	Memory
253171		Nightlight	Wish (LMIO19_noras)	C++14	100 / 100	194 ms	8188 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 = (long double)(q * y_1 - p * x_1) * -p / (q * q + p * p);
    yy = (long double)(q * y_1 - p * x_1) * q / (q * q + p * p);
//    cout << xx << " " << yy << "\n";
    //kalau tedekat > R
    if(xx * xx + yy * yy > R * R) continue;
    //kalau ga bakal ketemu yang terdekat
    if(((x_1 > x_2) ^ (x_1 > xx)) || ((y_1 > y_2) ^ (y_1 > yy)) || (x_1 == xx)) {
//    	cout << "A\n";
      if(x_1 * x_1 + y_1 * y_1 > R * R) continue;
      else {
        l = 0, r = limit;
        while(l <= r) {
          mid = (l + r) >> 1;
          if(check(mid)) {
            l = mid + 1;
            res = mid;
          }else r = mid - 1;
        }
        seg.emplace_back(0, 1);
        seg.emplace_back(res + 1, 0);
      }
    }else {
//    	cout << "B\n";
      //cari yang bawah dulu
      l = 0, r = floor((x_1 - xx) / (x_1 - x_2)), lb = -1;
      while(l <= r) {
        mid = (l + r) >> 1;
        if(check(mid)) {
          r = mid - 1;
          lb = mid;
        }else l = mid + 1;
      }
      l = lb, r = limit, ub = -1;
      if(lb == -1) l = ceil((x_1 - xx) / (x_1 - x_2));
      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 = floor((x_1 - xx) / (x_1 - x_2));
      if(lb == -1) lb = ceil((x_1 - xx) / (x_1 - x_2));
      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++;
    }
    ans = max(ans, cnt);
  }
  cout << ans << "\n";
  cin >> N;
}

Compilation message (stderr)

noras.cpp: In function 'int main()':
noras.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < seg.size() - 1;) {
                  ~~^~~~~~~~~~~~~~~~
noras.cpp:57:30: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
         seg.emplace_back(res + 1, 0);
                          ~~~~^~~

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