QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#132613#6378. LaLa and Monster Hunting (Part 1)UrgantTeam#RE 0ms0kbC++233.8kb2023-07-30 19:43:282023-07-30 19:43:29

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 19:43:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-30 19:43:28]
  • 提交

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: 0
Dangerous Syscalls

input:

3
-3 0 1
0 0 3
3 0 1

output:


result: