제출 #1247400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247400		tvgk	별자리 2 (JOI14_constellation2)	C++20	100 / 100	941 ms	824 KiB

constellation2

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e3 + 7;

struct point
{
    ll x, y;
    int c;

    point operator-(const point& b) const
    {
        point res;
        res.x = x - b.x;
        res.y = y - b.y;
        return res;
    }
};

int n;
ll cur[5], cnt[5];
point a[mxN], root;
vector<point> vc, V;

ll cross(point a, point b, point c)
{
    b = b - a;
    c = c - a;
    return b.x * c.y - b.y * c.x;
}

int half(point a)
{
    if (!a.x && !a.y)
        return -1;

    if (!a.x)
        return a.y < 0;
    return a.x < 0;
}

bool cmp(point a, point b)
{
    int u = half(a - root);
    int v = half(b - root);
    if (u != v)
        return u < v;
    return cross(root, a, b) < 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].c;
        cnt[a[i].c]++;
        V.push_back(a[i]);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        root = a[i];
        vc = V;
        sort(vc.begin(), vc.end(), cmp);

        int sz = vc.size();
        for (int j = 1; j < sz; j++)
            vc.push_back(vc[j]);

        cur[0] = cur[1] = cur[2] = 0;
        cur[root.c] = 1;
        int ctr = 1;
        for (int j = 1; j < sz; j++)
        {
            cur[vc[j].c]--;
            while (ctr < j + sz - 1 && cross(root, vc[j], vc[ctr]) <= 0)
            {
                cur[vc[ctr].c]++;
                ctr++;
            }

            ans += cur[(root.c + 1) % 3] * cur[(root.c + 2) % 3] * (cnt[(vc[j].c + 1) % 3] - cur[(vc[j].c + 1) % 3]) * (cnt[(vc[j].c + 2) % 3] - cur[(vc[j].c + 2) % 3]);
        }
    }
    cout << ans / 2;
}

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