QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788590 | #9668. Isoball: 2D Version | Andeviking | AC ✓ | 5ms | 3732kb | C++20 | 2.4kb | 2024-11-27 17:33:41 | 2024-11-27 17:33:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define range(x) (x).begin(), (x).end()
struct Point {
ll x, y;
Point() {};
Point(ll x, ll y)
: x(x), y(y)
{
}
Point operator-(Point B)
{
return Point(x - B.x, y - B.y);
}
};
ll cross(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
int sgn(ll x)
{
if (x < 0)
return -1;
else if (x == 0)
return 0;
else
return 1;
}
ll Dot(Point a, Point b)
{
return a.x * b.x + a.y * b.y;
}
bool Cross_segment(Point p1, Point p2, Point p3, Point p4)
{
bool cond_1 = max(p1.x, p2.x) < min(p3.x, p4.x);
bool cond_2 = max(p1.y, p2.y) < min(p3.y, p4.y);
bool cond_3 = max(p3.x, p4.x) < min(p1.x, p2.x);
bool cond_4 = max(p3.y, p4.y) < min(p1.y, p2.y);
if (cond_1 || cond_2 || cond_3 || cond_4) {
return false;
}
if ((__int128_t)cross(p3 - p1, p2 - p1) * cross(p4 - p1, p2 - p1) > 0 || (__int128_t)cross(p2 - p3, p4 - p3) * cross(p1 - p3, p4 - p3) > 0) {
return false;
}
return true;
}
void solve()
{
int x, y, r, vx, vy;
cin >> x >> y >> r >> vx >> vy;
int lx, ly, rx, ry;
cin >> lx >> ly >> rx >> ry;
lx += r, ly += r;
rx -= r, ry -= r;
if (rx < lx || ry < ly) {
cout << "No\n";
return;
}
Point a(x, y);
ll cnt = 0;
if (vx && vy)
cnt = min(10000000 / abs(vx), 10000000 / abs(vy));
else if (vx)
cnt = 10000000 / abs(vx);
else
cnt = 10000000 / abs(vy);
x += cnt * vx;
y += cnt * vy;
Point b(x, y);
// cout << a.x << ' ' << a.y << ' ' << b.x << ' ' << b.y << '\n';
Point cka(lx, ly), ckb(lx, ry);
if (Cross_segment(a, b, cka, ckb)) {
cout << "Yes\n";
return;
}
ckb.x = rx, ckb.y = ly;
if (Cross_segment(a, b, cka, ckb)) {
cout << "Yes\n";
return;
}
ckb.x = rx, ckb.y = ry;
cka.x = lx, cka.y = ry;
if (Cross_segment(a, b, cka, ckb)) {
cout << "Yes\n";
return;
}
cka.x = rx, cka.y = ly;
if (Cross_segment(a, b, cka, ckb)) {
cout << "Yes\n";
return;
}
cout << "No\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t--)
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
5 0 0 1 1 0 2 -2 6 2 0 0 1 1 0 2 0 6 2 0 0 1 1 1 1 1 3 3 0 0 1 -1 -1 1 1 3 3 0 0 1 -1 1 -5 -5 5 5
output:
Yes No Yes No Yes
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
2 0 0 1000000 1000000 1000000 -1000000 -1000000 1000000 1000000 1000000 1000000 1 -1000000 -1000000 -1000000 -1000000 -999999 -999999
output:
Yes No
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 5ms
memory: 3596kb
input:
10000 10 -10 10 1 -2 -13 -8 6 -1 -7 -10 3 3 1 -3 -12 14 -9 -9 -2 4 4 -3 -11 7 -8 12 -3 1 8 -1 0 -11 1 19 13 -1 8 9 -3 2 11 -5 17 4 -2 -7 3 -3 5 -12 -14 10 1 0 3 6 -5 3 -11 2 2 16 4 9 6 5 -4 -8 -11 18 -1 0 0 8 4 -2 -10 -15 1 12 8 4 4 5 2 -17 3 8 7 -3 7 10 -4 0 1 0 10 20 -6 -10 5 -3 -1 -20 -20 15 7 5 ...
output:
No No No No No Yes No No No No No Yes No Yes No No Yes No Yes No No No No No Yes No No No Yes No No No Yes No No Yes No No No No No No No No No No No No Yes No No No No No No No No No Yes Yes No No Yes Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes...
result:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 5ms
memory: 3660kb
input:
10000 435040 443595 65698 -909008 707638 -786096 -552413 -684992 853567 662291 -64591 243223 870386 898512 -302221 -384430 747067 -262550 -626562 -285970 945616 -695143 223635 14005 -632139 169681 481076 -955128 470568 284454 -511490 -623372 -465039 -713986 477856 -675726 304873 -693785 286659 -9272...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No Yes No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
10000 2 -1000000 1 0 1 -6 999998 1 1000000 0 -1000000 1 0 1 -3 999998 -1 999999 4 -1000000 1 0 1 -1 999996 6 999999 1 -1000000 1 0 -1 0 999998 2 999999 2 -1000000 1 0 1 -1 999997 4 999999 1 -1000000 1 0 1 -2 999998 2 1000000 -4 -1000000 1 0 1 -5 999997 -4 999999 -3 -1000000 1 0 1 -3 999996 -2 100000...
output:
No No Yes No Yes Yes No No No No No No No No No No No No No No No No No Yes No Yes No No No No No No Yes No No No No Yes No No No No No No No No No No No No No Yes No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No Yes Yes No No No No No No Yes Yes No No No No No N...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 4ms
memory: 3720kb
input:
10000 -1000000 -2 1 1 0 999998 -6 1000000 6 -1000000 -5 1 -1 0 999996 -2 1000000 3 -1000000 2 1 1 0 999998 0 999999 4 -1000000 -5 1 -1 0 999997 0 999998 5 -1000000 -3 1 -1 0 999997 -7 1000000 -2 -1000000 0 1 -1 0 999996 4 999997 6 -1000000 -2 1 1 0 999998 3 999999 6 -1000000 -3 1 -1 0 999996 -3 1000...
output:
Yes No No No No No No No No Yes No No No No No No No Yes No No No No No No No No No No No Yes Yes No No No No No No No No Yes No No No No No No No No No Yes No No No No Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No No No No Yes No No No No No Yes Ye...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 5ms
memory: 3732kb
input:
10000 -1000000 -1000000 39 2 0 19265 57834 60609 77684 -1000000 -1000000 22 -1 2 16667 94521 76708 97725 -1000000 -1000000 75 1 1 2120 9797 44577 47582 -1000000 -1000000 61 2 0 2400 15626 21867 21831 -1000000 -1000000 39 0 -1 32558 37142 66755 56056 -1000000 -1000000 64 1 2 33672 45285 53247 46521 -...
output:
No No Yes No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No No No No No No Yes No No No No No No No No Yes No No No No No No No No No Yes N...
result:
ok 10000 lines
Extra Test:
score: 0
Extra Test Passed