QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#820534	#4383. Laser	SGColin	AC ✓	29ms	4224kb	C++20	1.6kb	2024-12-18 21:44:20	2024-12-18 21:44:20

Judging History

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

[2024-12-18 21:44:20]
评测

测评结果：AC
用时：29ms
内存：4224kb

查看

[2024-12-18 21:44:20]
提交

answer

#include<bits/stdc++.h>
using namespace std;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 500007

int n;

struct point{int x, y;} c[N];

inline bool check(int x, int y) {
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        if (c[i].x == x) {
            ++cnt;
            if (c[i].y == y) continue;
        }
        if (c[i].y == y) ++cnt;
        if (c[i].x + c[i].y == x + y) ++cnt;
        if (c[i].x - c[i].y == x - y) ++cnt; 
    }
    return cnt == n;
}

inline bool check() {
    for (int i = 2; i <= n; ++i)
        if (c[i].x != c[1].x && c[i].y != c[1].y) {
            if (check(c[1].x, c[i].y)) return true;
            if (check(c[1].x, c[i].y - abs(c[i].x - c[1].x))) return true;
            if (check(c[1].x, c[i].y + abs(c[i].x - c[1].x))) return true;
            if (check(c[i].x, c[1].y)) return true;
            if (check(c[i].x - abs(c[i].y - c[1].y), c[1].y)) return true;
            if (check(c[i].x + abs(c[i].y - c[1].y), c[1].y)) return true;
            return false;
        }
    return true;
}

inline void work() {
    n = rd();
    for (int i = 1; i <= n; ++i) {
        c[i].x = rd(); c[i].y = rd();
    }
    if (check()) {puts("YES"); return;}
    for (int i = 1; i <= n; ++i) {
        c[i].x = c[i].x + c[i].y; 
        c[i].y = c[i].x - (c[i].y << 1);
    }
    if (check()) {puts("YES"); return;}
    puts("NO");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 29ms

memory: 4224kb

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