제출 #1164276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164276		OI_Account	Dragon 2 (JOI17_dragon2)	C++20	15 / 100	108 ms	25836 KiB

dragon2

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

#define X first
#define Y second

typedef long long ll;
typedef pair<ll, ll> point;

const int N = 3000;

int n, m, c[N + 10], ans[N + 10][N + 10];
point p[N + 10], st, en;

void readInput() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> p[i].X >> p[i].Y >> c[i];
    cin >> st.X >> st.Y;
    cin >> en.X >> en.Y;
}

point operator-(const point &p1, const point &p2) {
    return point(p1.X - p2.X, p1.Y - p2.Y);
}

ll operator^(const point &u, const point &v) {
    return u.X * v.Y - u.Y * v.X;
}

char direction(point p1, point p2, point p3) {
    ll cp = (p2 - p1) ^ (p3 - p1);
    if (cp == 0)
        return 's';
    return 0 < cp? 'l': 'r';
}

bool isCut(int i, int j) {
    bool q1 = (direction(p[i], st, en) == direction(p[i], st, p[j]));
    bool q2 = (direction(p[i], en, st) == direction(p[i], en, p[j]));
    return q1 && q2;
}

void calcAns() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (c[i] != c[j] && isCut(i, j))
                ans[c[i]][c[j]]++;
}

void solve() {
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        cout << ans[i][j] << '\n';
    }
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcAns();
    solve();
    return 0;
}

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