Untitled
unknown
c_cpp
9 months ago
1.3 kB
12
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