QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #56304 | #4383. Laser | qinjianbin# | AC ✓ | 115ms | 3612kb | C++11 | 2.5kb | 2022-10-18 16:57:27 | 2022-10-18 16:57:28 |
Judging History
answer
#include<iostream>
#include<set>
#define pii pair<long long, long long>
using namespace std;
const int MAXN = 5e5 + 10;
const int PA[4][2] = {{1, -1}, {1, 1}, {0, 1}, {1, 0}};
set<pii> points;
set<pii> points2;
struct Line {
long long a, b, c;
Line(long long a = 0, long long b = 0, long long c = 0): a(a), b(b), c(c) {}
}lin[10];
long long lnum = 0;
bool CheckP(long long a, long long b, long long c, long long x, long long y) {
if (a * x + b * y + c == 0) return true;
return false;
}
pii tmp;
bool GetP(long long idx, long long a, long long b, long long c) {
if (lin[idx].a == a && lin[idx].b == b) return false;
// printf("asd%d %d %d %d\n", a, b, lin[idx].a, lin[idx].b);
tmp.second = (lin[idx].a * c - a * lin[idx].c) / (a * lin[idx].b - lin[idx].a * b);
if (a == 0) tmp.first = (-lin[idx].b * tmp.second - lin[idx].c) / lin[idx].a;
else tmp.first = (-b * tmp.second - c) / a;
return true;
}
long long GetC(long long x, long long y, long long a, long long b) {
return -1 * (a * x + b * y);
}
int main() {
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
long long x, y;
scanf("%lld%lld", &x, &y);
if (n == 1) {puts("YES"); continue;}
lnum = 4;
for (int i = 0; i < 4; i++) {
lin[i].a = PA[i][0], lin[i].b = PA[i][1];
lin[i].c = GetC(x, y, PA[i][0], PA[i][1]);
}
points.insert(make_pair(x, y));
for (int i = 2; i <= n; i++) {
scanf("%lld%lld", &x, &y);
int j;
points2.clear();
int idxk;
bool flag = false;
for (j = 0; j < 4; j++) { //judge all line
long long a = PA[j][0], b = PA[j][1];
long long c = GetC(x, y, PA[j][0], PA[j][1]);
// printf("%d %d %d %d\n", i, a, b, c);
for (auto p : points) {
if (CheckP(a, b, c, p.first, p.second)) {
points2.insert(p);
}
}
for (int k = 0; k < lnum; k++) {
// printf("%d\n", k);
if (a == lin[k].a && b == lin[k].b && c == lin[k].c) {
flag = true;
idxk = k;
}
else if (GetP(k, a, b, c)) {
points2.insert(tmp);
}
}
// printf("%d\n", points2.size());
}
if (flag == false) lnum = 0;
else {
lnum = 1;
lin[0] = lin[idxk];
}
points = points2;
// printf("%d\n", lnum);
// for (j = 0; j < lnum; j++) {
// if (CheckL(j, x, y)) {
// break;
// }
// }
// if (j == lnum) //没有重合线
// lnum = 0;
// else {
// lnum = 1;
// lin[0] = lin[j];
// }
}
if (lnum || points.size()) {
puts("YES");
}
else puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 115ms
memory: 3612kb
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