Submission #1199261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199261		12345678	별자리 2 (JOI14_constellation2)	C++20	100 / 100	814 ms	800 KiB

constellation2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e3+5;

struct points
{
    ll x, y, c;
    points(ll x, ll y, ll c): x(x) ,y(y), c(c){}
    bool turnleft(const points &o) {return (x*o.y-y*o.x>0);}
    bool operator< (const points &o) const
    {
        if (y>=0&&o.y<0) return 1;
        if (y<0&&o.y>=0) return 0;
        return x*o.y-y*o.x>0;
    }
};

ll n, x[nx], y[nx], c[nx], res, tmp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i]>>c[i];
    for (int rt=1; rt<=n; rt++)
    {
        vector<points> v;
        for (int i=1; i<=n; i++) if (i!=rt) v.push_back(points(x[i]-x[rt], y[i]-y[rt], c[i]));
        sort(v.begin(), v.end());
        vector<ll> dn(3, 0), up(3, 0);
        deque<points> dq;
        for (auto pts:v)
        {
            if (pts.y>=0) up[pts.c]++;
            else dn[pts.c]++, dq.push_back(pts);
        }
        for (auto pts:v)
        {
            if (!dq.empty()&&dq.front().x==pts.x&&dq.front().y==pts.y) dn[dq.front().c]--, dq.pop_front();
            else up[pts.c]--;
            while (!dq.empty()&&pts.turnleft(dq.front())) dn[dq.front().c]--, up[dq.front().c]++, dq.pop_front();
            tmp=1;
            for (int i=0; i<3; i++) if (pts.c!=i) tmp*=dn[i];
            for (int i=0; i<3; i++) if (c[rt]!=i) tmp*=up[i];
            //cout<<"heref "<<tmp<<'\n';
            res+=tmp;
            tmp=1;
            for (int i=0; i<3; i++) if (pts.c!=i) tmp*=up[i];
            for (int i=0; i<3; i++) if (c[rt]!=i) tmp*=dn[i];
            //cout<<"heres "<<tmp<<'\n';
            res+=tmp;
            dq.push_back(pts);
            dn[pts.c]++;
            /*
            cout<<"after update\n";
            cout<<"up ";
            for (int i=0; i<3; i++) cout<<up[i]<<' ';
            cout<<'\n';
            cout<<"down ";
            for (int i=0; i<3; i++) cout<<dn[i]<<' ';
            cout<<'\n';
            cout<<"res "<<res<<'\n';*/
        }
        //cout<<"rt "<<rt<<' '<<res<<'\n';
    }
    cout<<res/4;
}

/*
7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2
*/

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