QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#47011#4383. LaserAsukaKyle#AC ✓399ms38184kbC++5.6kb2022-09-03 14:52:392022-09-03 14:52:40

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-03 14:52:40]
  • 评测
  • 测评结果:AC
  • 用时:399ms
  • 内存:38184kb
  • [2022-09-03 14:52:39]
  • 提交

answer

// Author:  HolyK
// Created: Sat Sep  3 13:53:32 2022
#include <bits/stdc++.h>

template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct Hash {
  size_t operator()(uint64_t x) const {
    x += 48;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};
using Map = gp_hash_table<uint64_t, int, Hash>;

void solve() {
  int n;
  std::cin >> n;
  Map hx, hy, hxpy, hxmy, hp;
  std::vector<PII> a(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    std::cin >> x >> y;
    hx[x]++;
    hy[y]++;
    hxpy[x + y]++;
    hxmy[x - y]++;
    hp[x * 1000000000LL + y]++;
    a[i] = {x, y};
  }

  auto get = [&](const Map &h, const uint64_t &x) {
    auto it = h.find(x);
    if (it != h.end()) {
      return it->second;
    }
    return 0;
  };
  
  auto check = [&](int x, int y) {
    PII p(x, y);
    return get(hx, x) + get(hy, y) + get(hxpy, x + y) + get(hxmy, x - y) - 3 * get(hp, x * 1000000000LL + y) == n;
  };

  auto check1 = [&](int xpy, int xmy) {
    int c = get(hxpy, xpy) + get(hxmy, xmy);
    if ((xpy ^ xmy ^ 1) & 1) {
      int x = xpy + xmy >> 1;
      int y = xpy - xmy >> 1;
      c += get(hx, x) + get(hy, y) - 3 * get(hp, x * 1000000000LL + y);
    }
    return c == n;
  };
  
  for (auto &p : a) {
    if (check(p.first, p.second)) {
      std::cout << "YES\n";
      return;
    }
  }

  std::sort(a.begin(), a.end(), [&](const PII &i, const PII &j) {
    return i.first < j.first;
  });
  
  for (int i = 0, j, k1 = -1e9, k2 = -1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].first == a[j].first; j++) ;
    if (i && (check(a[i].first, a[i].first - k1) || check(a[i].first, k2))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smax(k1, a[i].first - a[i].second);
      smax(k2, a[i].second);
    }
  }

  std::reverse(a.begin(), a.end());

  for (int i = 0, j, k1 = 1e9, k2 = 1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].first == a[j].first; j++) ;
    if (i && (check(a[i].first, a[i].first - k1) || check(a[i].first, k2))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smin(k1, a[i].first - a[i].second);
      smin(k2, a[i].second);
    }
  }

  std::sort(a.begin(), a.end(), [&](const PII &i, const PII &j) {
    return i.first - i.second < j.first - j.second;
  });
  
  for (int i = 0, j, k1 = 1e9, k2 = 1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].first - a[i].second == a[j].first - a[j].second; j++) ;
    if (i && (check(a[i].first - a[i].second + k1, k1) || check1(k2, a[i].first - a[i].second))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smin(k1, a[i].second);
      smin(k2, a[i].first + a[i].second);
    }
  }
  std::reverse(a.begin(), a.end());
  for (int i = 0, j, k1 = -1e9, k2 = -1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].first - a[i].second == a[j].first - a[j].second; j++) ;
    if (i && (check(a[i].first - a[i].second + k1, k1) || check1(k2, a[i].first - a[i].second))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smax(k1, a[i].second);
      smax(k2, a[i].first + a[i].second);
    }
  }

  std::sort(a.begin(), a.end(), [&](const PII &i, const PII &j) {
    return i.second < j.second;
  });

  for (int i = 0, j, k1 = -1e9, k2 = -1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].second == a[j].second; j++) ;
    if (i && (check(k1 - a[i].second, a[i].second) || check(k2, a[i].second))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smax(k1, a[i].first + a[i].second);
      smax(k2, a[i].first);
    }
  }
  std::reverse(a.begin(), a.end());
  for (int i = 0, j, k1 = 1e9, k2 = 1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].second == a[j].second; j++) ;
    if (i && (check(k1 - a[i].second, a[i].second) || check(k2, a[i].second))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smin(k1, a[i].first + a[i].second);
      smin(k2, a[i].first);
    }
  }

  
  std::sort(a.begin(), a.end(), [&](const PII &i, const PII &j) {
    return i.second + i.first < j.second + j.first;
  });

  for (int i = 0, j, k1 = -1e9, k2 = -1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].second + a[i].first == a[j].second + a[j].first; j++) ;
    if (i && (check(k1, a[i].first + a[i].second - k1) || check1(a[i].first + a[i].second, k2))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smax(k1, a[i].first);
      smax(k2, a[i].first - a[i].second);
    }
  }
  std::reverse(a.begin(), a.end());
   for (int i = 0, j, k1 = 1e9, k2 = 1e9; i < n; i = j) {
    for (j = i + 1; j < n && a[i].second + a[i].first == a[j].second + a[j].first; j++) ;
    if (i && (check(k1, a[i].first + a[i].second - k1) || check1(a[i].first + a[i].second, k2))) {
      std::cout << "YES\n";
      return; 
    }
    for (; i < j; i++) {
      smin(k1, a[i].first);
      smin(k2, a[i].first - a[i].second);
    }
  }

  std::cout << "NO\n";
}

int main() {
  // freopen("t.in", "r", stdin);
  
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int t = 1;
  
  std::cin >> t;
  
  while (t--) {
    solve();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 399ms
memory: 38184kb

input:

116
4
-10 0
10 0
5 5
-5 -5
4
-10 0
10 0
0 10
0 -10
4
-1 0
1 0
2 0
3 0
4
0 1
0 2
0 3
0 4
4
100 100
10000 10000
100000 100000
-100 -100
4
-100 100
-10000 10000
-100000 100000
100 -100
6
1 1
1 3
2 2
3 1
3 3
3 4
7
1 1
1 3
2 2
3 1
3 3
1 4
3 4
4
1236833 14678
1232056 9901
1237055 9790
1231834 15011
4
1236...

output:

YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
YES
NO
NO
YES
YES
NO
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
YES
NO
YES
NO...

result:

ok 116 lines