Submission #894674

#	Time	Username	Problem	Language	Result	Execution time	Memory
894674		OAleksa	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4064 ms	3464 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;
} a[N], s, e;
vector<point> g[N];
int n, m, q, c[N];
inline 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]) {
				int d5 = cross(s, e, u);
				for (auto t : g[b]) {
					//ili je u trouglu
					//ili se seku duzi
					int d = cross(u, s, t);
					int d1 = cross(s, e, t);
					int d2 = cross(e, u ,t);
					int d3 = cross(u, t, s);
					int d4 = cross(u, t, e);
					if (d == d1 && d1 == d2)
						++ans;
					else if (d3 != d4 && d5 != d1)
						++ans;
				}
			}
			cout << ans << '\n';
		}
  }
  return 0;
}

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