QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318944 | #5067. Two Walls | zlxFTH | WA | 1ms | 3752kb | C++17 | 2.5kb | 2024-02-01 11:40:54 | 2024-02-01 11:40:54 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(...) fprintf(stderr, __VA_ARGS__)
using db = long double;
constexpr db eps = 1e-14;
int dcmp(db x) {return x < -eps ? -1 : x > eps;}
struct Point {
db x, y;
Point(db x = 0, db 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*(db p) {return Point(x * p, y * p);}
db operator*(const Point &b) {return x * b.x + y * b.y;}
db operator^(const Point &b) {return x * b.y - y * b.x;}
db len() {return sqrt(*this * *this);}
bool operator==(const Point &b) {
return !dcmp(x - b.x) && !dcmp(y - b.y);
}
void read() {
int _x, _y;
cin >> _x >> _y;
x = _x, y = _y;
}
};
bool onLine(Point p, Point a, Point b) {
return dcmp((p - a) ^ (p - b)) == 0;
}
bool onSeg(Point p, Point a, Point b) {
return onLine(p, a, b) && dcmp((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 || dcmp((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;
}
Point p = c2 - c1, q = d2 - d1;
Point t1 = c1 + ((p.len() + eps) / p.len());
Point t2 = c2 - ((p.len() + eps) / p.len());
Point t3 = d1 + ((q.len() + eps) / q.len());
Point t4 = d2 - ((q.len() + eps) / q.len());
auto check = [&](Point a, Point b) {
return pd(a, b, c1, c2) && pd(a, b, d1, d2);
};
if (check(a, t1) && check(t1, b)
|| check(a, t2) && check(t2, b)
|| check(a, t3) && check(t3, b)
|| check(a, t4) && check(t4, b)) {
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: 3752kb
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: 3624kb
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:
1 1
result:
wrong answer 1st numbers differ - expected: '2', found: '1'