Untitled

 avatar
unknown
c_cpp
9 months ago
1.3 kB
14
Indexable
// clang-format off
#include <bits/stdc++.h>
using namespace std;
 
#define endl '\n'
typedef long long ll;
 
template <typename T> void print(T &v) {
  for (auto x : v)
    cout << x << ' ';
  cout << endl;
}
// clang-format on

typedef complex<ll> pt;
#define x() real()
#define y() imag()

ll cross(pt a, pt b) { return (conj(a) * b).y(); }
bool half(pt p) { return p.y() > 0 || (p.y() == 0 && p.x() < 0); }
ll choose2(ll n) { return n * (n - 1) / 2; }

void solve() {
  int n;
  cin >> n;
  vector<pt> a(n);
  for (int i = 0; i < n; i++) {
    ll x, y;
    cin >> x >> y;
    a[i] = {x, y};
  }

  vector<pt> b(2 * n - 2);
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0, k = 0; j < n; j++) {
      if (j != i)
        b[k++] = a[j] - a[i];
    }
    sort(b.begin(), b.begin() + n - 1, [](pt u, pt v) {
      return make_pair(half(u), 0ll) < make_pair(half(v), cross(u, v));
    });
    copy(b.begin(), b.begin() + n - 1, b.begin() + n - 1);

    int r = 0;
    for (int l = 0; l < n - 1; l++) {
      r = max(l + 1, r);
      while (cross(b[l], b[r]) > 0)
        r++;
      ll left = r - l - 1, right = n - left - 2;
      ans += choose2(left) * choose2(right);
    }
  }
  cout << ans / 2 << endl;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  int t = 1;
  while (t--)
    solve();

  return 0;
}
Editor is loading...
Leave a Comment