Submission #526754

#	Time	Username	Problem	Language	Result	Execution time	Memory
526754		pokmui9909	별자리 2 (JOI14_constellation2)	C++17	55 / 100	9053 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;
const lf PI = acos(-1);
 
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 pxj = X[j], pyi = Y[i];
    X[j] = Y[i] = 1;

    ans += X[0] * X[1] * X[2] * Y[0] * Y[1] * Y[2];
    X[j] = pxj, Y[i] = pyi;
}
  
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{
            Point P1 = A[a] - A[0], P2 = A[b] - A[0];
            lf A1 = atan2(P1.y, P1.x), A2 = atan2(P2.y, P2.x);
            if(A1 < 0) A1 += PI;
            if(A2 < 0) A2 += PI;
            if(A1 >= PI) A1 -= PI;
            if(A2 >= PI) A2 -= PI;
            return A1 < A2;
        });
        //for(auto i : V) cout <<">> "<< A[i].x << ' ' << A[i].y << '\n';
        // 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[j], A[k]);
                if(C > 0){
                    X[T[k]]++;
                } else {
                    Y[T[k]]++;
                }
            }
            //cout<<X[0]<<' '<<X[1]<<' '<<X[2]<<' '<<Y[0]<<' '<<Y[1]<<' '<<Y[2]<<'\n';
            add(X, Y, T[0], T[j]);
        }
    }
    cout << ans / 4;
}

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