이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |