結果

問題 No.2897 ２集合間距離
ユーザー vjudge1
提出日時 2024-09-25 15:57:58
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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