QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #47446 | #4383. Laser | Winner | AC ✓ | 117ms | 5940kb | C++11 | 2.1kb | 2022-09-09 20:59:01 | 2022-09-09 20:59:02 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e5 + 20;
const int mod = 1e9 + 7;
int t, n;
PII node[N];
int dx[4] = {1, 0, 1, 1};
int dy[4] = {0, 1, 1, -1};
PII find(int a1, int b1, int c1, int a2, int b2, int c2){
int y = (c2 * a1 - c1 * a2) / (b1 * a2 - b2 * a1);
int x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
return {x, y};
}
bool check(int x, int y){
for(int i = 1; i <= n; i++){
int xx = node[i].x, yy = node[i].y;
if(x == xx || y == yy) continue;
int nx = xx - x, ny = yy - y;
if(abs(nx) == abs(ny)) continue;
return false;
}
return true;
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d%d", &node[i].x, &node[i].y);
node[i].x *= 2;
node[i].y *= 2;
}
if(n == 1 || n == 2){
puts("YES");
continue;
}
PII node1 = node[1], node2;
int idx = 1;
while(++idx <= n){
node2 = node[idx];
int x1 = node1.x, x2 = node2.x, y1 = node1.y, y2 = node2.y;
if(x1 == x2 || y1 == y2) continue;
else if(abs(x1 - x2) == abs(y1 - y2)) continue;
else break;
}
if(idx > n){
puts("YES");
continue;
}
int x1 = node1.x, x2 = node2.x, y1 = node1.y, y2 = node2.y;
bool flag = false;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(i == j) continue;
int a1, b1, c1, a2, b2, c2;
if(i == 0){
a1 = 1, b1 = 0, c1 = -x1;
}
if(i == 1){
a1 = 1, b1 = -1, c1 = y1 - x1;
}
if(i == 2){
a1 = 0, b1 = 1, c1 = -y1;
}
if(i == 3){
a1 = 1, b1 = 1, c1 = -(x1 + y1);
}
if(j == 0){
a2 = 1, b2 = 0, c2 = -x2;
}
if(j == 1){
a2 = 1, b2 = -1, c2 = y2 - x2;
}
if(j == 2){
a2 = 0, b2 = 1, c2 = -y2;
}
if(j == 3){
a2 = 1, b2 = 1, c2 = -(x2 + y2);
}
PII res = find(a1, b1, c1, a2, b2, c2);
if(check(res.x, res.y)){
flag = true;
break;
}
}
if(flag) break;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 117ms
memory: 5940kb
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