結果

問題 No.2897 ２集合間距離
ユーザー vjudge1vjudge1
提出日時 2024-09-25 15:57:58
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 196 ms / 3,500 ms
コード長 1,479 bytes
コンパイル時間 3,307 ms
コンパイル使用メモリ 246,960 KB
実行使用メモリ 26,400 KB
最終ジャッジ日時 2024-09-25 15:58:07
合計ジャッジ時間 7,182 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
21,864 KB
testcase_01 AC 69 ms
21,868 KB
testcase_02 AC 71 ms
23,908 KB
testcase_03 AC 84 ms
23,908 KB
testcase_04 AC 86 ms
23,908 KB
testcase_05 AC 90 ms
23,912 KB
testcase_06 AC 83 ms
24,044 KB
testcase_07 AC 78 ms
23,912 KB
testcase_08 AC 81 ms
23,904 KB
testcase_09 AC 88 ms
24,032 KB
testcase_10 AC 81 ms
24,052 KB
testcase_11 AC 105 ms
24,092 KB
testcase_12 AC 74 ms
23,932 KB
testcase_13 AC 74 ms
24,184 KB
testcase_14 AC 77 ms
25,200 KB
testcase_15 AC 78 ms
25,404 KB
testcase_16 AC 190 ms
26,400 KB
testcase_17 AC 195 ms
26,276 KB
testcase_18 AC 191 ms
26,280 KB
testcase_19 AC 180 ms
26,276 KB
testcase_20 AC 185 ms
26,280 KB
testcase_21 AC 184 ms
25,428 KB
testcase_22 AC 196 ms
25,000 KB
testcase_23 AC 175 ms
26,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define _1 (__int128)1

using namespace std;
using ll = long long;

void FileIO (const string s) {
  freopen(string(s + ".in").c_str(), "r", stdin);
  freopen(string(s + ".out").c_str(), "w", stdout);
}

const int N = 2e5 + 10;

int n, x[N], y[N], m, x_[N], y_[N], l, r = 2000, sum[2010][2010];
bool f[2010][2010];

bool check (int dis) {
  for (int i = 0; i <= 2000; i++)
    for (int j = 0; j <= 2000; j++)
      sum[i][j] = 0;
  for (int i = 1; i <= n; i++)
    sum[max(0, x[i] - dis)][max(0, y[i] - dis)]++, sum[max(0, x[i] - dis)][min(2000, y[i] + dis) + 1]--, sum[min(2000, x[i] + dis) + 1][max(0, y[i] - dis)]--, sum[min(2000, x[i] + dis) + 1][min(2000, y[i] + dis) + 1]++;
  for (int i = 0; i <= 2000; i++)
    for (int j = 1; j <= 2000; j++)
      sum[i][j] += sum[i][j - 1];
  for (int i = 1; i <= 2000; i++)
    for (int j = 0; j <= 2000; j++)
      sum[i][j] += sum[i - 1][j];
  for (int i = 0; i <= 2000; i++)
    for (int j = 0; j <= 2000; j++)
      if (sum[i][j] && f[i][j])
        return 1;
  return 0;
}

signed main () {
  ios::sync_with_stdio(0), cin.tie(0);
  // FileIO("");
  cin >> n;
  for (int i = 1, a, b; i <= n; i++)
    cin >> a >> b, x[i] = a + b, y[i] = a - b + 1000;
  cin >> m;
  for (int i = 1, a, b; i <= m; i++)
    cin >> a >> b, x_[i] = a + b, y_[i] = a - b + 1000, f[x_[i]][y_[i]] = 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) r = mid;
    else l = mid + 1;
  }
  cout << l;
  return 0;
}
0