Submission #558396

#	Time	Username	Problem	Language	Result	Execution time	Memory
558396		fatemetmhr	Dragon 2 (JOI17_dragon2)	C++17	15 / 100	124 ms	31504 KiB

dragon2

// Be name khoda //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<ll> point;

#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define pb          push_back


const int maxn5 = 4e3 + 10;
const int maxnt = 4e5 + 10;

point p[maxn5];
int cnt[maxn5][maxn5], ty[maxn5];

inline bool pari(ll a){
    return a > 0;
}

inline ll crossz(point a, point b){
    return real(a) * imag(b) - imag(a) * real(b);
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, q; cin >> n >> m;

    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y >> ty[i];
        p[i] = {x, y};
    }

    int x, y; cin >> x >> y;
    point a = {x, y};
    cin >> x >> y;
    point b = {x, y};

    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(ty[i] != ty[j]){
        ll salp = crossz(p[i] - a, p[j] - p[i]), m = crossz(b - a, p[j] - p[i]);
        ll sbet = crossz(p[i] - a, b - a);
        //cout << i << ' ' << j << ' ' << salp << ' ' << sbet << ' ' << m << endl;
        if(m == 0)
            continue;
        if((pari(salp) == pari(m) || salp == 0) && (pari(m) ? salp <= m : salp >= m) && (pari(sbet) == pari(m) || sbet == 0)){
            cnt[ty[i]][ty[j]]++;
            //cout << "we found " << i << ' ' << j << endl;
        }
    }

    cin >> q;
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        cout << cnt[a][b] << '\n';
    }
}

/*
3 3 1
3 2 6
1 4 5
3 3
*/

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