Submission #157213

#	Time	Username	Problem	Language	Result	Execution time	Memory
157213		Flying_dragon_02	별자리 2 (JOI14_constellation2)	C++14	100 / 100	1986 ms	504 KiB

constellation2

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;

const int N = 3005;

int n;

long long sum;

iii x[N];

vector<iii> vec;

int ccw(iii a, iii b, iii p) {
    long long sum = (1ll * b.fi.fi - 1ll * a.fi.fi) * (1ll * b.fi.se - 1ll * p.fi.se) - (1ll * b.fi.se - 1ll * a.fi.se) * (1ll * b.fi.fi - 1ll * p.fi.fi);
    if(sum < 0) // ben trai
        return -1;
    else if(sum == 0) // thang long
        return 0;
    else // ben phai
        return 1;
}

bool compare(iii x) {
    if(x.fi.se > 0)
        return 1;
    else if(x.fi.se == 0 && x.fi.fi > 0)
        return 1;
    return 0;
}

iii lmao;

bool cmp(iii a, iii b) {
    if(compare(a) != compare(b)) return compare(a) > compare(b);
    return ccw(lmao, a, b) > 0;
}

long long used[5], total[5];

long long calc(int x, int y) {
    long long val1, val2;
    total[y]--;
    total[x]--;
    if(x == 0)
        val1 = used[1] * used[2];
    if(x == 1)
        val1 = used[0] * used[2];
    if(x == 2)
        val1 = used[0] * used[1];
    if(y == 0)
        val2 = (total[1] - used[1]) * (total[2] - used[2]);
    if(y == 1)
        val2 = (total[0] - used[0]) * (total[2] - used[2]);
    if(y == 2)
        val2 = (total[0] - used[0]) * (total[1] - used[1]);
    total[y]++;
    total[x]++;
    //cout << val1 * val2 << "\n";
    return val1 * val2;
}

void process(int id) {
    vec.clear();
    memset(used, 0, sizeof(used));
    for(int i = 1; i <= n; i++) {
        if(i != id)
            vec.pb({{x[i].fi.fi - x[id].fi.fi, x[i].fi.se - x[id].fi.se}, x[i].se});
    }
    sort(vec.begin(), vec.end(), cmp);
    /*if(id == 3) {
        for(int i = 0; i < vec.size(); i++)
            cout << vec[i].fi.fi << " " << vec[i].fi.se << " " << vec[i].se << "\n";
    }*/
    int pter1 = 0, m = vec.size();
    //exit(0);
    //cout << 0 << " " << pter1 << " " << used[0] << " " << used[1] << " " << used[2] << "\n";
    for(int i = 0; i < vec.size(); i++) {
        --used[vec[i].se];
        if(i == pter1) {used[vec[pter1].se]++; pter1 = (pter1 + 1) % m;}
        while(ccw(lmao, vec[i], vec[pter1]) > 0) {
            //cout << "wtf\n";
            used[vec[pter1].se]++;
            pter1 = (pter1 + 1) % m;
        }
        //if(ccw(lmao, vec[i], vec[i - 1]) < 0)
            //used[vec[i - 1].se]--;
        //cout << i << " " << pter1 << " " << used[0] << " " << used[1] << " " << used[2] << " " << vec[i - 1].se << "\n";
        sum += calc(x[id].se, vec[i].se);
    }
    //cout << sum << "\n";
    //exit(0);
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i].fi.fi >> x[i].fi.se >> x[i].se;
        total[x[i].se]++;
    }
    for(int i = 1; i <= n; i++)
        process(i);
    cout << sum / 2;
}
/*7
0 0 0
2 0 1
1 2 2
-2 1 0
-2 -3 0
0 -2 1
2 -2 2*/

Compilation message (stderr)

constellation2.cpp: In function 'void process(int)':
constellation2.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~
constellation2.cpp: In function 'long long int calc(int, int)':
constellation2.cpp:69:19: warning: 'val2' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return val1 * val2;
                   ^~~~
constellation2.cpp:69:19: warning: 'val1' may be used uninitialized in this function [-Wmaybe-uninitialized]

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