Submission #527699

#	Time	Username	Problem	Language	Result	Execution time	Memory
527699		pokmui9909	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1280 ms	1348 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;
}
ll sign(Point p){
    return Point(0, 0) < p;
}
  
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> X(3), Y(3);
        vector<pair<Point, ll>> V;
        for(int j = 1; j < N; j++){
            V.push_back({A[j] - A[0], T[j]});
            X[T[j]]++;
        }
        sort(V.begin(), V.end(), [&](pair<Point, ll> a, pair<Point, ll> b) -> bool{
            if(sign(a.x) != sign(b.x)) return sign(a.x) > sign(b.x);
            else return CCW(Point(0, 0), a.x, b.x) >= 0;
        });
        for(int j = 0; j < N - 1; j++) V.push_back(V[j]);
        for(int j = 0, k = 0; j < N - 1; j++){
            while(k < j + N - 1 && CCW(Point(0, 0), V[j].x, V[k].x) >= 0){
                X[V[k].y]--, Y[V[k].y]++;
                k++;
            }
            add(X, Y, T[0], V[j].y);
            X[V[j].y]++, Y[V[j].y]--;
        }
    }
    cout << ans / 2;
}

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