QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132603 | #6378. LaLa and Monster Hunting (Part 1) | UrgantTeam# | WA | 2ms | 7692kb | C++23 | 3.9kb | 2023-07-30 18:33:20 | 2023-07-30 18:33:23 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
const ld EPS = 1e-9;
struct triple
{
pair <ld, ld> vec;
int typ;
};
pair <int, int> center[1000005], point[1000005];
int rad[1000005];
ll dist(pair <int, int> A)
{
return (ll) A.x * A.x + (ll) A.y * A.y;
}
ll vecs(pair <int, int> A, pair <int, int> B)
{
return (ll) A.x * B.y - (ll) A.y * B.x;
}
ld vecsld(pair <ld, ld> A, pair <ld, ld> B)
{
return A.x * B.y - A.y * B.x;
}
bool cmp(pair <ld, ld> A, pair <ld, ld> B)
{
bool fl1 = (A.y > 0) || (fabs(A.y) < EPS && A.x > 0);
bool fl2 = (B.y > 0) || (fabs(B.y) < EPS && B.x > 0);
if (fl1 != fl2) return fl1;
return vecsld(A, B) > 0;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> center[i].x >> center[i].y >> rad[i];
point[i] = center[i];
}
for (int i = 1; i <= n; i++)
{
ll d = dist(center[i]);
if (d <= (ll) rad[i] * rad[i]) cout << "Yes\n", exit(0);
}
sort(point + 1, point + n + 1, [] (pair <int, int> A, pair <int, int> B) {
return (A.y < B.y) || (A.y == B.y && A.x < B.x);
});
pair <int, int> start = point[1];
sort(point + 2, point + n + 1, [start] (pair <int, int> A, pair <int, int> B) {
pair <int, int> S = mp(A.x - start.x, A.y - start.y);
pair <int, int> T = mp(B.x - start.x, B.y - start.y);
if (vecs(S, T) > 0) return true;
if (vecs(S, T) < 0) return false;
return dist(S) < dist(T);
});
vector <pair <int, int> > obol;
for (int i = 1; i <= n; i++)
{
pair <int, int> A = point[i];
while ((int) obol.size() > 1)
{
pair <int, int> B = obol.back();
obol.pop_back();
pair <int, int> C = obol.back();
pair <int, int> S = mp(A.x - B.x, A.y - B.y);
pair <int, int> T = mp(B.x - C.x, B.y - C.y);
if (vecs(T, S) > 0)
{
obol.pb(B);
break;
}
}
obol.pb(A);
}
obol.pb(point[1]);
bool inside = false, outside = false;
for (int i = 0; i < (int) obol.size() - 1; i++)
{
pair <int, int> A = obol[i], B = obol[i + 1];
pair <int, int> S = mp(B.x - A.x, B.y - A.y);
pair <int, int> T = mp(-A.x, -A.y);
if (vecs(S, T) < 0) outside = true;
if (vecs(S, T) > 0) inside = true;
}
if (inside && !outside) cout << "Yes\n", exit(0);
vector <triple> result;
for (int i = 1; i <= n; i++)
{
ll A = -center[i].x, B = -center[i].y, C = dist(center[i]) - (ll) rad[i] * rad[i];
ld zn = sqrtl(A * A + B * B);
ld dists = (A * center[i].x + B * center[i].y + C) / zn;
pair <ld, ld> nap = mp(dists * A / zn, dists * B / zn);
pair <ld, ld> pt = mp(center[i].x - nap.x, center[i].y - nap.y);
ld len = sqrtl((ll) rad[i] * rad[i] - dists * dists);
pair <ld, ld> vdol = mp(-B / zn * len, A / zn * len);
pair <ld, ld> P = mp(pt.x + vdol.x, pt.y + vdol.y);
pair <ld, ld> Q = mp(pt.x - vdol.x, pt.y - vdol.y);
if (vecsld(P, Q) < 0) swap(P, Q);
result.pb({P, 1});
result.pb({Q, -1});
if (!cmp(P, Q) && cmp(Q, P)) result.pb({mp(1, 0), 1});
result.pb({mp(-P.x, -P.y), 0});
result.pb({mp(-Q.x, -Q.y), 0});
//cout << P.x << ' ' << P.y << '\n';
//cout << Q.x << ' ' << Q.y << '\n';
}
sort(result.begin(), result.end(), [] (triple A, triple B) {
bool neq = (cmp(A.vec, B.vec) || cmp(B.vec, A.vec));
if (!neq)
{
return A.typ > B.typ;
}
return cmp(A.vec, B.vec);
});
//for (const auto &[vec, typ] : result) cout << vec.x << ' ' << vec.y << ' ' << typ << '\n';
int bal = 0;
for (const auto &[vec, typ] : result)
{
//cout << vec.x << ' ' << vec.y << ' ' << typ << '\n';
bal += typ;
if (typ == 0 && bal > 0) cout << "Yes\n", exit(0);
}
cout << "No\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7604kb
input:
3 -3 0 1 0 0 3 3 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 2ms
memory: 7568kb
input:
3 2 0 1 0 2 1 -5 -5 3
output:
Yes
result:
ok answer is YES
Test #3:
score: 0
Accepted
time: 0ms
memory: 7612kb
input:
1 3 3 1
output:
No
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 2ms
memory: 7608kb
input:
1 -3 -2 5
output:
Yes
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
2 1 3 5 -2 -6 1
output:
Yes
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 1ms
memory: 7632kb
input:
3 -14 7 7 2 -1 3 8 -1 9
output:
Yes
result:
ok answer is YES
Test #7:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
4 5 -3 9 -10 6 5 4 2 2 -8 10 2
output:
Yes
result:
ok answer is YES
Test #8:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
5 -2 -1 4 9 10 5 -9 2 4 6 -3 5 0 -4 10
output:
Yes
result:
ok answer is YES
Test #9:
score: 0
Accepted
time: 2ms
memory: 7576kb
input:
6 -3 -1 6 3 1 8 1 2 4 1 -3 5 3 7 4 5 5 4
output:
Yes
result:
ok answer is YES
Test #10:
score: 0
Accepted
time: 1ms
memory: 7536kb
input:
7 3 -2 5 -1 10 7 -1 10 3 1 -5 5 -9 -9 4 -5 -10 5 1 4 9
output:
Yes
result:
ok answer is YES
Test #11:
score: 0
Accepted
time: 1ms
memory: 7684kb
input:
8 3 -1 5 1 7 2 -2 -10 6 -1 6 4 -2 0 9 0 9 6 -7 1 7 5 -2 7
output:
Yes
result:
ok answer is YES
Test #12:
score: 0
Accepted
time: 1ms
memory: 7580kb
input:
9 -1 0 8 2 0 8 -8 -10 2 8 -2 1 -5 -8 0 -2 -3 5 -7 -4 9 -3 9 8 -10 10 7
output:
Yes
result:
ok answer is YES
Test #13:
score: 0
Accepted
time: 1ms
memory: 7692kb
input:
10 -3 0 4 3 -1 8 7 0 6 -6 -10 2 4 5 2 -7 -5 0 -7 4 7 10 7 0 -3 0 9 7 -6 6
output:
Yes
result:
ok answer is YES
Test #14:
score: 0
Accepted
time: 1ms
memory: 7588kb
input:
11 0 -4 7 5 9 4 -8 0 2 -10 8 5 7 9 1 7 8 8 4 -8 5 8 6 9 2 -7 8 3 4 0 10 -8 10
output:
Yes
result:
ok answer is YES
Test #15:
score: 0
Accepted
time: 2ms
memory: 7644kb
input:
12 2 3 5 -5 -9 5 5 -10 3 9 -10 9 -4 -10 0 10 5 1 -3 -5 7 2 10 10 0 7 10 -10 -7 5 -7 1 9 0 4 8
output:
Yes
result:
ok answer is YES
Test #16:
score: 0
Accepted
time: 1ms
memory: 7572kb
input:
13 3 0 5 -12 0 4 2 2 8 6 3 4 5 -3 0 3 -4 9 -9 5 9 -1 -3 5 4 -1 2 1 -3 10 -10 2 3 -7 9 7 -6 9 3
output:
Yes
result:
ok answer is YES
Test #17:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
14 2 1 4 8 -3 0 -7 -4 2 10 -6 5 -4 -4 4 1 1 2 4 6 5 -3 -5 5 10 -10 1 4 -6 2 -4 9 3 -3 10 8 -6 6 10 8 -8 1
output:
Yes
result:
ok answer is YES
Test #18:
score: 0
Accepted
time: 2ms
memory: 7640kb
input:
15 1 2 6 -1 -2 3 9 -10 2 0 5 6 8 10 8 -2 -6 9 -7 4 0 6 -10 1 -6 -3 10 7 -3 2 5 -9 5 10 0 3 9 -6 1 0 -1 3 -8 -3 5
output:
Yes
result:
ok answer is YES
Test #19:
score: 0
Accepted
time: 1ms
memory: 7612kb
input:
16 0 -8 9 1 -4 0 -8 -3 7 -6 -7 7 3 -7 9 -9 7 10 4 1 1 -9 2 7 1 -7 7 -5 -3 3 4 4 3 -1 -9 2 -4 -1 7 -8 -2 10 -6 1 3 -1 -8 3
output:
Yes
result:
ok answer is YES
Test #20:
score: 0
Accepted
time: 2ms
memory: 7568kb
input:
17 0 4 7 -6 8 0 6 6 4 3 -8 7 -6 2 6 -10 8 3 -10 9 8 -9 1 9 -10 8 2 -9 0 7 -5 1 1 2 -4 5 -3 -5 0 -4 0 6 1 -2 0 6 -4 4 -2 -7 3
output:
Yes
result:
ok answer is YES
Test #21:
score: 0
Accepted
time: 1ms
memory: 7572kb
input:
18 -3 -3 1 5 5 8 7 -6 8 -10 3 4 10 1 2 7 -10 10 3 -4 9 1 5 6 -10 -4 1 3 -4 2 4 -5 9 3 -6 4 3 1 7 9 -3 5 6 9 8 5 -6 2 9 -2 5 10 3 2
output:
Yes
result:
ok answer is YES
Test #22:
score: 0
Accepted
time: 2ms
memory: 7576kb
input:
19 4 -1 8 -5 5 1 -5 -4 7 -9 -10 7 -8 6 0 10 10 6 2 -6 9 1 1 6 -9 -6 7 -8 -5 5 2 -7 9 1 -1 4 -7 4 5 -3 3 10 1 6 6 2 4 6 -7 3 10 -5 -4 8 9 -4 6
output:
Yes
result:
ok answer is YES
Test #23:
score: 0
Accepted
time: 2ms
memory: 7612kb
input:
20 1 0 2 -10 3 7 9 -3 7 0 -10 7 7 -6 8 -5 6 7 5 6 5 7 8 8 -4 -10 9 -8 -10 8 2 -5 5 -5 -5 9 -5 9 10 1 9 1 -7 6 4 0 -1 6 -5 7 9 -1 -4 5 -4 4 6 3 6 2
output:
Yes
result:
ok answer is YES
Test #24:
score: 0
Accepted
time: 1ms
memory: 7576kb
input:
3 -6 -6 2 -10 -8 8 -7 -7 5
output:
No
result:
ok answer is NO
Test #25:
score: 0
Accepted
time: 2ms
memory: 7576kb
input:
4 -7 -9 3 -3 -6 2 9 -1 2 0 -7 3
output:
No
result:
ok answer is NO
Test #26:
score: 0
Accepted
time: 1ms
memory: 7568kb
input:
5 2 -6 3 -2 -8 2 -3 -5 1 -5 -9 1 0 -7 1
output:
No
result:
ok answer is NO
Test #27:
score: 0
Accepted
time: 1ms
memory: 7584kb
input:
6 10 9 6 7 10 3 6 10 8 3 7 3 -4 8 3 7 5 4
output:
No
result:
ok answer is NO
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 7592kb
input:
7 -9 8 6 -8 1 4 -10 -1 1 -7 10 4 -5 9 1 -8 10 6 -10 9 5
output:
Yes
result:
wrong answer expected NO, found YES