oj.uz

Submission #526754

# Submission time Handle Problem Language Result Execution time Memory
526754 2022-02-16T03:59:47 Z pokmui9909 별자리 2 (JOI14_constellation2) C++17
55 / 100
 9000 ms 368 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 324 KB Output is correct
2 Correct 4 ms 204 KB Output is correct
3 Correct 11 ms 332 KB Output is correct
4 Correct 49 ms 332 KB Output is correct
5 Correct 61 ms 328 KB Output is correct
6 Correct 200 ms 332 KB Output is correct
7 Correct 207 ms 332 KB Output is correct
8 Correct 221 ms 332 KB Output is correct
9 Correct 193 ms 332 KB Output is correct
10 Correct 119 ms 332 KB Output is correct
11 Correct 167 ms 332 KB Output is correct
12 Correct 160 ms 324 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2610 ms 352 KB Output is correct
2 Correct 3495 ms 356 KB Output is correct
3 Correct 4740 ms 368 KB Output is correct
4 Correct 4834 ms 364 KB Output is correct
5 Execution timed out 9053 ms 340 KB Time limit exceeded
6 Halted 0 ms 0 KB -