QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318923 | #5067. Two Walls | zlxFTH | WA | 1ms | 3732kb | C++17 | 1.9kb | 2024-02-01 11:02:32 | 2024-02-01 11:02:32 |
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);}
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() {
cin >> x >> 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;
}
Point inter(Point a, Point b, Point c, Point d) {
Point x = b - a, y = d - c, z = a - c;
return a + x * ((y ^ z) / (x ^ y));
}
void solve() {
auto pd = [&](Point a, Point b, Point c, Point d) {
Point p = b - a, q = d - c;
if ((p ^ q) == 0) {
if (onSeg(c, a, b) || onSeg(d, a, b)) return false;
return true;
}
Point i = inter(a, b, c, d);
return !onSeg(i, a, b) || !onSeg(i, c, d);
};
Point a, b, c1, c2, d1, d2;
a.read();
b.read();
c1.read(), c2.read();
d1.read(), d2.read();
if (pd(a, b, c1, c2) && pd(a, b, d1, d2)) {
cout << 0 << "\n";
return;
}
if (c1 == c2 || d1 == d2 || ((c2 - c1) ^ (d2 - d1)) == 0) {
cout << 1 << "\n";
return;
}
Point i = inter(c1, c2, d1, d2);
if (!onSeg(i, c1, c2) || !onSeg(i, d1, d2)) {
cout << 1 << "\n";
return;
}
if (pd(a, c1, d1, d2) && pd(c1, b, d1, d2)
|| pd(a, c2, d1, d2) && pd(c2, b, d1, d2)
|| pd(a, d1, c1, c2) && pd(d1, b, c1, c2)
|| pd(a, d2, c1, c2) && pd(d2, b, c1, c2)) {
cout << 1 << "\n";
return;
} else {
cout << 2 << '\n';
return;
}
}
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: 3732kb
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: -100
Wrong Answer
time: 0ms
memory: 3732kb
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:
0 0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'