Submission #104426

#	Time	Username	Problem	Language	Result	Execution time	Memory
104426		KiKoS	Relay (COI16_relay)	C++17	0 / 100	8 ms	5248 KiB

relay

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#ifdef DEBUG
	const int MAXN = 10;
	const int MAXLOG = 4;
	const int MAXSQRT = 4;
#else
	const int MAXN = 3e5;
	const int MAXLOG = 20;
	const int MAXSQRT = 400;
	#define cerr if (false) cerr
#endif

mt19937 rng(time(0));
#define int ll
const int INF = 1e9;
const int MOD = 1e9 + 7;


struct V {
	int x, y;
	V() {

	}
	V(int a, int b) {
		x = a, y = b;
	}
};

V operator + (V a, V b) {
	return V(a.x + b.x, a.y + b.y);
}

V operator - (V a, V b) {
	return V(a.x - b.x, a.y - b.y);
}

int operator ^ (V a, V b) {
	return a.x * b.y - a.y * b.x;
}

int operator * (V a, V b) {
	return a.x * b.x + a.y * b.y;
}

istream & operator >> (istream &in, V &a) {
	in >> a.x >> a.y;
	return in;
}

ostream & operator << (ostream &out, V a) {
	out << a.x << ' ' << a.y;
	return out;
}

int n, m;

V polygon[MAXN];
V dots[MAXN];
int dist[MAXN];

int D(V a, V b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool check(V a, V b) {
	cerr << "check " << a << '\t' << b << '\n';
	int pos_1 = -1;
	int pos_2 = -1;
	{
		cerr << "pos_1\n";
		int l = 0;
		int r = n;
		while (l + 1 < r) {
			cerr << l << ' ' << r << '\n';
			int mid = (l + r) >> 1;
			if (((polygon[mid] - a) ^ (polygon[0] - a)) < 0) {
				l = mid;
				continue;
			}
			cerr << "here\n";
			if (((polygon[mid] - a) ^ (polygon[(mid + 1) % n] - polygon[mid])) >= 0) {
				r = mid;
			}
			else {
				l = mid;
			}
		}
		for (int i = 0; i < min(n, 5ll); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
		for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
		for (int i = max(0ll, n - 5); i < n; i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
		for (int i = 0; i < min(n, 5ll); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
		for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
		for (int i = max(0ll, n - 5); i < n; i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
	}

	{
		int l = 0;
		int r = n;
		cerr << "pos_2\n";
		while (l + 1 < r) {
			cerr << l << ' ' << r << '\n';
			int mid = (l + r) >> 1;
			if (((polygon[mid] - a) ^ (polygon[0] - a)) > 0) {
				r = mid;
				continue;
			}
			if (((a - polygon[mid]) ^ (polygon[(mid + 1) % n] - polygon[mid])) >= 0) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		for (int i = 0; i < min(n, 5ll); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
		for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
		for (int i = max(0ll, n - 5); i < n; i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = a - polygon[i];
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_2 = i;
			}
		}
		for (int i = 0; i < min(n, 5ll); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
		for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
		for (int i = max(0ll, n - 5); i < n; i++) {
			V A = polygon[(i + 1) % n] - polygon[i];
			V B = polygon[i] - polygon[(i + n - 1) % n];
			V C = polygon[i] - a;
			bool _a = (C ^ A) >= 0;
			bool _b = (B ^ C) >= 0;
			bool _c = (A * C) > 0;
			cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
			if (_a && _b){// && _c) {
				pos_1 = i;
			}
		}
	}
	int idx = 0;
	// while (pos_1 < 0 || pos_2 < 0) {
	// 	cerr << "u were keked\n";
	// 	idx += idx | idx + 1;
	// }
	if (idx) {
		cout << idx << '\n';
	}
	assert(pos_1 != -1);
	assert(pos_2 != -1);
	cerr << pos_1 << ' ' << pos_2 << '\n';
	{
		V A = polygon[pos_2] - a;
		V B = polygon[pos_1] - a;
		V C = b - a;
		bool _a = (C ^ A) > 0;
		bool _b = (B ^ C) > 0;
		bool _c = (A * C) > 0;
		cerr << _a << ' ' << _b << '\n';
		if (!_a || !_b) {
			return 1;
		}
	}
	return 0;
	// int l = 0;
	// int r = n - 1;
	// while (l + 1 < r) {
	// 	int mid = (l + r) 
	// }
	// int pos_1 = l;

}

inline void init() {
	for (int i = 0; i < MAXN; i++) {
		dist[i] = INF;
	}
}

inline void solve() {
	init();
	for (int i = 0; i < m; i++) {
		cin >> dots[i];
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> polygon[i];
	}
	queue<int> q;
	q.push(0);
	dist[0] = 0;
	while (q.size()) {
		int v = q.front();
		q.pop();
		for (int i = 1; i < m; i++) {
			if (dist[i] != INF) {
				continue;
			}
			if (check(dots[v], dots[i]) || check(dots[i], dots[v])) {
				dist[i] = dist[v] + 1;
				q.push(i);
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		cerr << dist[i] << ' ';
		if (dist[i] <= 2 && dist[i] > 0) {
			ans++;
		}
	}
	cerr << '\n';
	cout << ans << '\n';
}

signed main() {
	#ifdef DEBUG
		freopen("C.in", "r", stdin);
		freopen("C.out", "w", stdout);
	#else
	
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while (cin >> m)
		solve();
	return 0;
}

Compilation message (stderr)

relay.cpp: In function 'bool check(V, V)':
relay.cpp:294:8: warning: unused variable '_c' [-Wunused-variable]
   bool _c = (A * C) > 0;
        ^~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43