QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#47011 | #4383. Laser | AsukaKyle# | AC ✓ | 399ms | 38184kb | C++ | 5.6kb | 2022-09-03 14:52:39 | 2022-09-03 14:52:40 |
Judging History
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;
}
详细
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