Submission #526706

#	Time	Username	Problem	Language	Result	Execution time	Memory
526706		pokmui9909	별자리 2 (JOI14_constellation2)	C++17	55 / 100	9068 ms	368 KiB

constellation2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
using Point = pair<ll, ll>;
Point operator+ (Point p, Point q) {return Point(p.x + q.x, p.y + q.y);}
Point operator- (Point p, Point q) {return Point(p.x - q.x, p.y - q.y);}
ll    operator* (Point p, Point q) {return p.x * q.x + p.y * q.y;}
ll    operator/ (Point p, Point q) {return p.x * q.y - q.x * p.y;}
 
ll CCW(Point p, Point q, Point r) {return (q - p) / (r - q);}
 
ll N;
Point A[3005];
ll T[3005];
ll ans = 0;

void add(vector<ll> &X, vector<ll> &Y, ll i, ll j){
    ll pxi = X[i], pyj = Y[j];
    X[i] = Y[j] = 1;

    ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
    X[i] = pxi, Y[j] = pyj;

    X[j] = Y[i] = 1;
    ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
}
  
int main(){
    cin.tie(0) -> sync_with_stdio(false);
    
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i].x >> A[i].y;
        cin >> T[i];
    }
    for(int i = 0; i < N; i++){
        swap(A[0], A[i]);
        swap(T[0], T[i]);
        vector<ll> V;
        for(int j = 1; j < N; j++){
            V.push_back(j);
        }
        sort(V.begin(), V.end(), [&](ll a, ll b) -> bool{
            return CCW(A[0], A[a], A[b]) > 0;
            // return CCW(A[0], A[a], A[b]) < CCW(A[0], A[b], A[a]);
        });
        // test_code
        for(auto j : V){
            vector<ll> X(3), Y(3);
            for(int k = 1; k < N; k++){
                if(k == j) continue;
                ll C = CCW(A[0], A[k], A[j]);
                if(C > 0){
                    X[T[k]]++;
                } else {
                    Y[T[k]]++;
                }
            }
            add(X, Y, T[0], T[j]);
        }
    }
    cout << ans / 4;
}

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