제출 #1164277

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

dragon2

#pragma GCC optimize("O2,unroll-loops,Ofast")
#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 = 30000;

int n, m, c[N + 10];
point p[N + 10], st, en;
vector<int> vec[N + 10];

void readInput() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].X >> p[i].Y >> c[i];
        vec[c[i]].push_back(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 solve() {
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        int cnt = 0;
        for (auto x: vec[i])
            for (auto y: vec[j])
            cnt += isCut(x, y);
        cout << cnt << '\n';
    }
    cout.flush();
}

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

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