QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#132614 | #6378. LaLa and Monster Hunting (Part 1) | UrgantTeam# | WA | 2ms | 7768kb | C++23 | 3.8kb | 2023-07-30 19:43:57 | 2023-07-30 19:44:00 |
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-15;
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 > EPS) || (fabs(A.y) < EPS && A.x > EPS);
bool fl2 = (B.y > EPS) || (fabs(B.y) < EPS && B.x > EPS);
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;
ld zn = sqrtl(A * A + B * B);
ld dists = (-1.0) * rad[i] * rad[i] / 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7608kb
input:
3 -3 0 1 0 0 3 3 0 1
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 7636kb
input:
3 2 0 1 0 2 1 -5 -5 3
output:
Yes
result:
ok answer is YES
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 7768kb
input:
1 3 3 1
output:
3.52052 2.14615 2.14615 3.52052 No
result:
wrong output format YES or NO expected, but 3.52052 found