Submission #157203

#	Time	Username	Problem	Language	Result	Execution time	Memory
157203		atoiz	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1338 ms	640 KiB

constellation2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <numeric>
#include <tuple>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ios>
#include <iomanip>
#include <random>
#include <chrono>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
#define SZ(a) ((int) a.size());
#define ALL(a) begin(a), end(a)

const int MAXN = 3007;

struct Point
{
    int x, y, c;
    Point(int _x = 0, int _y = 0, int _c = 0): x(_x), y(_y), c(_c) {};
    friend Point operator-(Point p1, Point p2) { return Point(p1.x - p2.x, p1.y - p2.y); }
    friend ll operator^(Point p1, Point p2) { return 1ll * p1.x * p2.y - 1ll * p2.x * p1.y; }
    int ccw(Point p1, Point p2)
    {
        ll x = (p1 - (*this)) ^ (p2 - (*this));
        if (x < 0) return -1;
        if (x > 0) return 1;
        return 0;
    }

} pnts[MAXN], pnts2[MAXN * 2];
int cnt[3], cnt1[3], total[3], N;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    FOR(i, 0, N - 1) {
        cin >> pnts[i].x >> pnts[i].y >> pnts[i].c;
        ++total[pnts[i].c];
    }
    ll ans = 0;
    FOR(i, 0, N - 1) {
        Point P = pnts[i];
        FOR(j, 0, i - 1) pnts2[j] = pnts[j];
        FOR(j, i + 1, N - 1) pnts2[j - 1] = pnts[j];
        sort(pnts2, pnts2 + N - 1, [&](Point p1, Point p2) {
            p1 = p1 - P, p2 = p2 - P;
            bool b1 = (p1.y < 0 || p1.y == 0 && p1.x < 0);
            bool b2 = (p2.y < 0 || p2.y == 0 && p2.x < 0);
            if (b1 != b2) return b1 < b2;
            return (p1 ^ p2) > 0;
        });
        copy(pnts2, pnts2 + N - 1, pnts2 + N - 1);

        memset(cnt, 0, sizeof cnt);
        for (int j = 0, k = 0; j < N - 1; ++j) {
            for (; k < j + N - 1 && P.ccw(pnts2[j], pnts2[k]) >= 0; ++k) ++cnt[pnts2[k].c];
            --cnt[pnts2[j].c];

            FOR(k, 0, 2) cnt1[k] = total[k] - cnt[k];
            int c1 = P.c, c2 = pnts2[j].c;
            --cnt1[c1], --cnt1[c2];

            // cerr << i << ": " << j << ' ' << k << endl;
            // FOR(k, 0, 2) cerr << cnt[k] << ' ';
            // FOR(k, 0, 2) cerr << cnt1[k] << ' ';
            // cerr << endl;

            ans += 1ll * cnt[(c1 + 1) % 3] * cnt[(c1 + 2) % 3] * cnt1[(c2 + 1) % 3] * cnt1[(c2 + 2) % 3];
            ans += 1ll * cnt1[(c1 + 1) % 3] * cnt1[(c1 + 2) % 3] * cnt[(c2 + 1) % 3] * cnt[(c2 + 2) % 3];
        }
    }
    cout << ans / 4 << endl;
}

Compilation message (stderr)

constellation2.cpp: In lambda function:
constellation2.cpp:68:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             bool b1 = (p1.y < 0 || p1.y == 0 && p1.x < 0);
                                    ~~~~~~~~~~^~~~~~~~~~~
constellation2.cpp:69:46: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
             bool b2 = (p2.y < 0 || p2.y == 0 && p2.x < 0);
                                    ~~~~~~~~~~^~~~~~~~~~~

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