Submission #1593598

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair< int, int >;

double eps = 1e-10;

int main() {
    int n;
    cin >> n;

    vector<ll> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    ll c=0, d=0;
    rep(i, n) {
        vector<double> a;
        rep(j, n) {
            if (j != i) a.push_back(atan2(y[j]-y[i], x[j]-x[i]));
        }
        sort(a.begin(), a.end());
        rep(j, n-1) a.push_back(a[j] + M_PI*2);
        rep(j, n-1) {
            int x = lower_bound(a.begin(), a.end(), a[j] + M_PI/2 - eps) - a.begin();
            int y = upper_bound(a.begin(), a.end(), a[j] + M_PI/2 + eps) - a.begin();
            int z = lower_bound(a.begin(), a.end(), a[j] + M_PI) - a.begin();
            c += y - x;
            d += z - y;
        }
    }

    ll e = (ll)n * (n-1) * (n-2) / 6 - c - d;
    cout << e << ' ' << c << ' ' << d << endl;
}

Submission Info

Judge Result