Submission #48096

#	Time	Username	Problem	Language	Result	Execution time	Memory
48096		choikiwon	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1563 ms	1896 KiB

constellation2

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

typedef long long ll;
typedef pair<int, int> pii;

ll cross(pii a, pii b) {
    return 1LL * a.first * b.second - 1LL * a.second * b.first;
}

int N;
struct Point {
    int x, y, c;
};
Point P[3010];
vector<pair<pii, int> > Q;
int cnt[2][3];

bool cmp(pair<pii, int> a, pair<pii, int> b) {
    return cross(a.first, b.first) > 0;
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].c);
    }

    ll ans = 0;
    for(int i = 0; i < N; i++) {
        Q.clear();
        for(int j = 0; j < N; j++) {
            if(i == j) continue;
            int dx = P[j].x - P[i].x;
            int dy = P[j].y - P[i].y;
            if(dy < 0) dy = -dy, dx = -dx;
            else if(dy == 0 && dx < 0) dx = -dx;

            Q.push_back({ {dx, dy}, j });
        }
        sort(Q.begin(), Q.end(), cmp);

        memset(cnt, 0, sizeof(cnt));
        for(int j = 1; j < Q.size(); j++) {
            int idx = Q[j].second;
            int dy = P[idx].y - P[i].y;
            if(dy > 0) cnt[1][ P[idx].c ]++;
            else cnt[0][ P[idx].c ]++;
        }

        int idx = Q[0].second;
        ll tmp = 1;
        for(int j = 0; j < 3; j++) if(j != P[idx].c) tmp *= cnt[0][j];
        for(int j = 0; j < 3; j++) if(j != P[i].c) tmp *= cnt[1][j];
        ans += tmp;

        for(int j = 1; j < Q.size(); j++) {
            int dx = P[idx].x - P[i].x;
            int dy = P[idx].y - P[i].y;
            if(dy > 0 || (dy == 0 && dx > 0)) cnt[0][ P[idx].c ]++;
            else cnt[1][ P[idx].c ]++;

            idx = Q[j].second;
            dy = P[idx].y - P[i].y;
            if(dy > 0) cnt[1][ P[idx].c ]--;
            else cnt[0][ P[idx].c ]--;

            ll tmp = 1;
            for(int k = 0; k < 3; k++) if(k != P[idx].c) tmp *= cnt[0][k];
            for(int k = 0; k < 3; k++) if(k != P[i].c) tmp *= cnt[1][k];
            ans += tmp;
        }
    }
    ans /= 2;
    printf("%lld", ans);
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:45:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < Q.size(); j++) {
                        ~~^~~~~~~~~~
constellation2.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < Q.size(); j++) {
                        ~~^~~~~~~~~~
constellation2.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
constellation2.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &P[i].x, &P[i].y, &P[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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