QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319102 | #5067. Two Walls | zlxFTH | WA | 92ms | 3708kb | C++17 | 2.5kb | 2024-02-01 20:38:03 | 2024-02-01 20:38:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Point {
i64 x, y;
Point(i64 x = 0, i64 y = 0) : x(x), y(y) {}
Point operator+(const Point &b) {return Point(x + b.x, y + b.y);}
Point operator-(const Point &b) {return Point(x - b.x, y - b.y);}
Point operator*(i64 p) {return Point(x * p, y * p);}
i64 operator*(const Point &b) {return x * b.x + y * b.y;}
i64 operator^(const Point &b) {return x * b.y - y * b.x;}
bool operator==(const Point &b) {
return x == b.x && y == b.y;
}
void read() {
int _x, _y;
cin >> _x >> _y;
x = _x, y = _y;
}
};
bool onLine(Point p, Point a, Point b) {
return ((p - a) ^ (p - b)) == 0;
}
bool onSeg(Point p, Point a, Point b) {
return onLine(p, a, b) && (p - a) * (p - b) <= 0;
}
void solve() {
auto icmp = [&](i64 x) {
return x < 0 ? -1 : x > 0;
};
auto pd = [&](Point a, Point b, Point c, Point d) {
if (onSeg(c, a, b) || onSeg(d, a, b)) return 1;
Point x = b - a, y = d - c;
if (icmp(x ^ (c - a)) * icmp(x ^ (d - a)) < 0 && icmp(y ^ (a - c)) * icmp(y ^ (b - c)) < 0) {
return 2;
} else {
return 0;
}
};
auto check2 = [&](Point a, Point b, Point c, Point d) {
if (((b - a) ^ (d - c)) == 0) return 0;
if (icmp((b - d) * (c - d)) < 0 || icmp((d - b) * (a - b)) < 0) return 1;
return 0;
};
Point a, b, c1, c2, d1, d2;
a.read();
b.read();
c1.read(), c2.read();
d1.read(), d2.read();
if (a == b || pd(a, b, c1, c2) == 0 && pd(a, b, d1, d2) == 0) {
cout << 0 << "\n";
} else {
if (((c2 - c1) ^ (b - a)) == 0 || ((d2 - d1) ^ (b - a)) == 0) {
cout << 1 << "\n";
} else {
auto check = [&](Point a, Point b) {
return pd(a, b, c1, c2) != 2 && pd(a, b, d1, d2) != 2;
};
if (check(a, c1) && check(c1, b)
|| check(a, c2) && check(c2, b)
|| check(a, d1) && check(d1, b)
|| check(a, d2) && check(d2, b)) {
cout << 1 << "\n";
} else {
if (check(a, c1) && check(b, d1) && check2(a, c1, b, d1)
|| check(a, c1) && check(b, d2) && check2(a, c1, b, d2)
|| check(a, c2) && check(b, d1) && check2(a, c2, b, d1)
|| check(a, c2) && check(b, d2) && check2(a, c2, b, d2)) {
cout << 1 << '\n';
} else {
cout << 2 << "\n";
}
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
3 0 0 1 1 2 2 3 3 4 4 5 5 0 0 1 1 2 2 3 3 2 2 3 3 0 0 10 10 10 0 0 10 1 1 2 2
output:
0 0 1
result:
ok 3 number(s): "0 0 1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
2 -999999999 999999998 999999999 999999998 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000 -1000000000 1000000000 -999999999 999999998 999999999 999999998 -999999998 -999999998 1000000000 1000000000 999999998 -999999998 -1000000000 1000000000
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 0 0 1 1 2 2 3 3 4 4 5 5
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 92ms
memory: 3708kb
input:
100000 -851839419 34688642 -667081997 395784949 -624068418 -155389155 119194510 -758711821 -992436155 -812775173 851861070 -592596572 974613003 -179673992 -485749861 520596304 -115838823 -265233646 -573799007 -222234500 608830643 -887109945 483106217 -906910755 -597593284 384264657 940783 476657007 ...
output:
0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 1 ...
result:
wrong answer 296th numbers differ - expected: '1', found: '2'