제출 #624850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624850		dutinmeow	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	2794 ms	3968 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;

struct point {
	long long x, y;

	point() : x(0), y(0) {}

	point(long long _x, long long _y) : x(_x), y(_y) {}

	point &operator+=(const point &rhs) { 
		x += rhs.x;
		y += rhs.y;
		return *this;
	}

	point &operator-=(const point &rhs) { 
		x -= rhs.x;
		y -= rhs.y;
		return *this;
	}
};

point make_point(long long x, long long y) { return point(x, y); }

point operator+(point lhs, const point &rhs) { return lhs += rhs; }

point operator-(point lhs, const point &rhs) { return lhs -= rhs; }

int operator^(const point &lhs, const point &rhs) { return lhs.x * rhs.y - lhs.y * rhs.x; }

bool ccw(const point &a, const point &b, const point &c) { 
	// return ((c - a) ^ (b - a)) < 0; 
	return (c.x - a.x) * (b.y - a.y) < (c.y - a.y) * (b.x - a.x);
}

bool ccw(const point &b, const point &c) { return ccw(point(), b, c); }

bool cpt(const point &a, const point &b, const point &c) {
	if (ccw(b, c))
		return ccw(b, a) && ccw(a, c);
	else 
		return ccw(a, b) && ccw(c, a);
}

int main() {
	int N, M;
	cin >> N >> M;
	vector<vector<point>> cat(M);
	for (int i = 0; i < N; i++) {
		long long x, y;
		int c;
		cin >> x >> y >> c;
		cat[c - 1].emplace_back(x, y);
	}

	long long sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	point S(sx, sy), T(tx, ty);

	int Q;
	cin >> Q;
	while (Q--) {
		int c1, c2;
		cin >> c1 >> c2;
		c1--, c2--;
		long long ans = 0;
		for (const point &p : cat[c1])
			for (const point &q : cat[c2])
				ans += int(cpt(q - p, S - p, T - p));
		cout << ans << '\n';
	}
}

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