Submission #172334

#	Time	Username	Problem	Language	Result	Execution time	Memory
172334		maruii	Dragon 2 (JOI17_dragon2)	C++14	15 / 100	4090 ms	2296 KiB

dragon2

#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 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40