제출 #1202197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202197		JooDdae	별자리 2 (JOI14_constellation2)	C++20	100 / 100	850 ms	580 KiB

constellation2

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

struct point {
    ll x, y;
    int c;
  
    point operator - (const point &o) const {
        return {x-o.x, y-o.y};
    }
};

ll cross(point a, point b) {
    return a.x*b.y - b.x*a.y;
}
  
int ccw(const point &a, const point &b, const point &c) {
    auto re = cross(b-a, c-a);
    return (re > 0) - (re < 0);
}
  
bool upper(const point &o, const point &a) {
    return a.x > o.x || (a.x == o.x && a.y > o.y);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N; cin >> N;
    vector<point> V(N);
    for(auto &[x, y, c] : V) cin >> x >> y >> c;

    vector<int> cnt(3, 0);
    for(auto [x, y, c] : V) cnt[c]++;

    ll ans = 0;

    for(int i=0;i<N;i++) {
        auto v = V; v.erase(v.begin() + i);
        auto o = V[i];
        int n = v.size();
  
        sort(v.begin(), v.end(), [&](const auto &a, const auto &b){
            if(upper(o, a) != upper(o, b)) return upper(o, a);
            return ccw(o, a, b) < 0;
        });

        vector<int> cL = cnt, cR = {0, 0, 0};
        cL[o.c]--;

        for(int i=0, j=0;i<n;i++) {
            if(i == j) cL[v[j].c]--, cR[v[j].c]++, j = (j+1)%n;
            while(ccw(v[i], o, v[j]) > 0) cL[v[j].c]--, cR[v[j].c]++, j = (j+1)%n;
            cR[v[i].c]--;

            auto c1 = 3^o.c, c2 = 3^v[i].c;
            ans += 1ll * (cL[c1&1] * cL[c1&2]) * (cR[c2&1] * cR[c2&2]);

            cL[v[i].c]++;
        }
    }

    cout << ans/2;
}

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