제출 #894654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894654		OAleksa	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4003 ms	4676 KiB

dragon2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 3e4 + 69;
struct point {
	int x, y;
};
point a[N];
point s, e;
int n, m, d1, e1, d2, e2, q, c[N];
vector<point> g[N];
int cross(point a, point b, point c) {
	point v = {b.x - a.x, b.y - a.y};
	point v1 = {c.x - a.x, c.y - a.y};
	int r = v1.x * v.y - v1.y * v.x;
	assert(r != 0);
	if (r > 0)
		return 1; //desno
	return -1; //levo
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
		cin >> n >> m;
		for (int i = 1;i <= n;i++) {
			cin >> a[i].x >> a[i].y >> c[i];
			g[c[i]].push_back(a[i]);
		}
		cin >> s.x >> s.y >> e.x >> e.y;
		cin >> q;
		while (q--) {
			int a, b;
			cin >> a >> b;
			int ans = 0;
			for (auto u : g[a]) {
				for (auto t : g[b]) {
					//ili je u trouglu
					//ili se seku duzi
					if (cross(u, s, t) == cross(s, e, t) && cross(s, e, t) == cross(e, u, t))
						++ans;
					else if (cross(u, t, s) != cross(u, t, e) && cross(s, e, u) != cross(s, e, t))
						++ans;
				}
			}
			cout << ans << '\n';
		}
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 0 / 40