Submission #1209224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209224		urejgi	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	1480 ms	2208 KiB

dragon2

#pragma GCC optimize("O3,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native,fma")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct pt{
    ll x,y;
    pt() : x(0),y(0) {}
    pt(ll _x, ll _y) : x(_x), y(_y) {}
    pt operator-(const pt&b) const{
        return pt(x-b.x, y-b.y);
    }
};

inline bool ccw(const pt&a, const pt&b, const pt&c){
    return (c.x - a.x)*(b.y - a.y) < (c.y - a.y)*(b.x - a.x);
}

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

inline bool inside(const pt&a, const pt&b, const pt&c){
    if(ccw(b,c)) return ccw(b,a) && ccw(a,c);
    else return ccw(a,b) && ccw(c,a);
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    vector<vector<pt>> v(m);
    for(int i = 0; i < n; i++){
        ll x,y; cin >> x >> y;
        int c; cin >> c;
        v[c-1].emplace_back(x,y);
    }
    ll sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty;
    pt S(sx,sy), T(tx,ty);
    int q; cin >> q;
    while(q-->0){
        int c1,c2; cin >> c1 >> c2;
        --c1,--c2;
        ll ans = 0ll;
        for(const pt&p:v[c1]){
            for(const pt&q:v[c2]){
                ans += int(inside(q-p,S-p,T-p));
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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