QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#132603#6378. LaLa and Monster Hunting (Part 1)UrgantTeam#WA 2ms7692kbC++233.9kb2023-07-30 18:33:202023-07-30 18:33:23

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-30 18:33:23]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7692kb
  • [2023-07-30 18:33:20]
  • 提交

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