Submission #157204

#	Time	Username	Problem	Language	Result	Execution time	Memory
157204		EntityIT	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1963 ms	604 KiB

constellation2

#include<bits/stdc++.h>

using namespace std;

using LL = long long;
const int NStar = (int)3e3 + 5;

int nStar;
LL ans;
vector<int> num(3, 0);

struct Star {
    int x, y, c;
    Star(int _x = 0, int _y = 0, int _c = 0) : x(_x), y(_y), c(_c) {}
    Star operator-(const Star &_) const { return Star(x - _.x, y - _.y, c); }
    Star operator+(const Star &_) const { return Star(x + _.x, y + _.y, c); }
    LL operator^(const Star &_) const { return (LL)x * _.y - (LL)y * _.x; }
    bool operator<(const Star &_) const {
        auto up = [&](Star a) { return a.y > 0 || (!a.y && a.x > 0); };
        if (up(*this) != up(_) ) return up(*this) > up(_);
        else return (*this ^ _) > 0;
    }
    void print() { cerr << x << ' ' << y << ' ' << c << '\n'; }
} initStar[NStar];

int main() {
//    freopen("input", "r", stdin);

    scanf(" %d", &nStar);
    for (int i = 1; i <= nStar; ++i) {
        scanf(" %d %d %d", &initStar[i].x, &initStar[i].y, &initStar[i].c);
        ++num[ initStar[i].c ];
    }

    for (int origin = 1; origin <= nStar; ++origin) {
//        initStar[origin].print();
        vector<Star> star;
        for (int i = 1; i <= nStar; ++i) if (i != origin) {
            star.push_back(initStar[i] - initStar[origin]);
        }
        sort(star.begin(), star.end() );
//        for (auto aStar : star) (aStar + initStar[origin]).print(); cerr << '\n';

        vector<int> cnt(3, 0);
        auto nxt = [&](int _i, int _n) { return _i == _n - 1 ? 0 : _i + 1; };

        for (int i = 0, j = 0; i < (int)star.size(); ++i) {
            --cnt[ star[i].c ];
            if (i == j) {
                ++cnt[ star[j].c ];
                j = nxt(j, (int)star.size() );
            }
            while (j != i && (star[i] ^ star[j]) > 0) {
                ++cnt[ star[j].c ];
                j = nxt(j, (int)star.size() );
            }
            vector<int> L = cnt, R(3, 0);
            for (int c = 0; c < 3; ++c) R[c] = num[c] - cnt[c];
            --R[ initStar[origin].c ]; --R[ star[i].c ];
            LL ret = 1;
            for (int c = 0; c < 3; ++c) if (c != star[i].c) ret *= L[c];
            for (int c = 0; c < 3; ++c) if (c != initStar[origin].c) ret *= R[c];
//            cerr << i << ' ' << j << "  ==  ";
//            for (int c = 0; c < 3; ++c) cerr << L[c] << ' ';
//            for (int c = 0; c < 3; ++c) cerr << R[c] << ' '; cerr << '\n';
            ans += ret;
        }
//        cerr << "ans = " << ans << '\n';
    }

    cout << ans / 2;

    return 0;
}

Compilation message (stderr)

constellation2.cpp: In function 'int main()':
constellation2.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &nStar);
     ~~~~~^~~~~~~~~~~~~~~
constellation2.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %d %d %d", &initStar[i].x, &initStar[i].y, &initStar[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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