oj.uz

Submission #104427

# Submission time Handle Problem Language Result Execution time Memory
104427 2019-04-06T18:39:10 Z KiKoS Relay (COI16_relay) C++17
18 / 100
 2000 ms 6396 KB 
#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];

bool check(V a, V b) {
	cerr << "check " << a << '\t' << b << '\n';
	int pos_1 = -1;
	for (int i = 0; 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 pos_2 = -1;
	for (int i = 0; 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;
		}
	}
	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

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 2808 KB Output is correct
2 Correct 666 ms 2688 KB Output is correct
3 Correct 209 ms 2808 KB Output is correct
4 Correct 303 ms 2808 KB Output is correct
5 Correct 355 ms 2780 KB Output is correct
6 Correct 338 ms 2808 KB Output is correct
7 Correct 171 ms 2936 KB Output is correct
8 Correct 114 ms 2808 KB Output is correct
9 Correct 281 ms 2764 KB Output is correct
10 Correct 293 ms 2808 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 2808 KB Output is correct
2 Correct 666 ms 2688 KB Output is correct
3 Correct 209 ms 2808 KB Output is correct
4 Correct 303 ms 2808 KB Output is correct
5 Correct 355 ms 2780 KB Output is correct
6 Correct 338 ms 2808 KB Output is correct
7 Correct 171 ms 2936 KB Output is correct
8 Correct 114 ms 2808 KB Output is correct
9 Correct 281 ms 2764 KB Output is correct
10 Correct 293 ms 2808 KB Output is correct
11 Execution timed out 2062 ms 2944 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 2808 KB Output is correct
2 Correct 666 ms 2688 KB Output is correct
3 Correct 209 ms 2808 KB Output is correct
4 Correct 303 ms 2808 KB Output is correct
5 Correct 355 ms 2780 KB Output is correct
6 Correct 338 ms 2808 KB Output is correct
7 Correct 171 ms 2936 KB Output is correct
8 Correct 114 ms 2808 KB Output is correct
9 Correct 281 ms 2764 KB Output is correct
10 Correct 293 ms 2808 KB Output is correct
11 Execution timed out 2065 ms 6396 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 2808 KB Output is correct
2 Correct 666 ms 2688 KB Output is correct
3 Correct 209 ms 2808 KB Output is correct
4 Correct 303 ms 2808 KB Output is correct
5 Correct 355 ms 2780 KB Output is correct
6 Correct 338 ms 2808 KB Output is correct
7 Correct 171 ms 2936 KB Output is correct
8 Correct 114 ms 2808 KB Output is correct
9 Correct 281 ms 2764 KB Output is correct
10 Correct 293 ms 2808 KB Output is correct
11 Execution timed out 2062 ms 2944 KB Time limit exceeded
12 Halted 0 ms 0 KB -