oj.uz

Submission #172334

# Submission time Handle Problem Language Result Execution time Memory
172334 2020-01-01T09:54:20 Z maruii Dragon 2 (JOI17_dragon2) C++14
15 / 100
 4000 ms 2296 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int ccw(pii a, pii b, pii c) {
	b = {b.ff - a.ff, b.ss - a.ss}, c = {c.ff - a.ff, c.ss - a.ss};
	long long t = 1ll * b.ff * c.ss - 1ll * b.ss * c.ff;
	return (t > 0) - (t < 0);
}

int N, M, Q;
vector<pii> P[30005];
pii X, Y;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		int a, b, c; cin >> a >> b >> c;
		P[c].emplace_back(a, b);
	}
	int d1, e1, d2, e2; cin >> d1 >> e1 >> d2 >> e2;
	X = {d1, e1}, Y = {d2, e2};
	cin >> Q;
	while (Q--) {
		int a, b; cin >> a >> b;
		int cnt = 0;
		for (auto i : P[a]) {
			for (auto j : P[b]) {
				if (ccw(i, j, X) != ccw(i, j, Y)) {
					if (ccw(i, j, X) < 0) swap(X, Y);
					if (ccw(X, Y, i) < 0) cnt++;
				}
			}
		}
		printf("%d\n", cnt);
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1144 KB Output is correct
2 Correct 48 ms 1144 KB Output is correct
3 Correct 64 ms 1228 KB Output is correct
4 Correct 43 ms 2168 KB Output is correct
5 Correct 38 ms 2296 KB Output is correct
6 Correct 4 ms 1272 KB Output is correct
7 Correct 5 ms 1272 KB Output is correct
8 Correct 21 ms 1240 KB Output is correct
9 Correct 18 ms 1144 KB Output is correct
10 Correct 21 ms 1144 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2723 ms 2168 KB Output is correct
2 Execution timed out 4090 ms 2040 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1144 KB Output is correct
2 Correct 48 ms 1144 KB Output is correct
3 Correct 64 ms 1228 KB Output is correct
4 Correct 43 ms 2168 KB Output is correct
5 Correct 38 ms 2296 KB Output is correct
6 Correct 4 ms 1272 KB Output is correct
7 Correct 5 ms 1272 KB Output is correct
8 Correct 21 ms 1240 KB Output is correct
9 Correct 18 ms 1144 KB Output is correct
10 Correct 21 ms 1144 KB Output is correct
11 Correct 2723 ms 2168 KB Output is correct
12 Execution timed out 4090 ms 2040 KB Time limit exceeded
13 Halted 0 ms 0 KB -