7e95b77fd5b74548fbb8c194ae1e9b5dd128ab9803a6bf1723e2ea6905525adf
// https://szkopul.edu.pl/problemset/problem/1M2UtUN-WqIVZu5YBXvVvrJw/site/?key=statement
#include <bits/stdc++.h>
// #define GARY_DBG
#define GARY_LIB
#define int int64_t
constexpr int sizik = 3500;
#define ar std::array
typedef std::vector<std::vector<int>> _kra;
namespace seg_tree {
int d[4 * sizik];
void build(int v, int tl, int tr) {
d[v] = 0;
if (tl != tr) {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
}
}
void update(int v, int tl, int tr, int x) {
if (tl == tr) {
d[v] += 1;
} else {
int tm = (tl + tr) / 2;
if (x <= tm) {
update(2 * v, tl, tm, x);
} else {
update(2 * v + 1, tm + 1, tr, x);
}
d[v] = d[2 * v] + d[2 * v + 1];
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) return d[v];
int tm = (tl + tr) / 2;
return query(2 * v, tl, tm, l, std::min(r, tm)) + query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
}
} // namespace seg_tree
struct Point {
int x, y;
};
struct Event {
bool isEnd;
Point p;
};
using P = std::pair<int, int>;
inline int z(int a) {
return a > 0 ? a : -a;
}
void solve() {
int n;
std::cin >> n;
std::vector<Point> points(n);
for (auto& [x, y] : points) {
std::cin >> x >> y;
}
std::map<P, std::vector<P>> mp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int dy = points[j].y - points[i].y;
int dx = points[j].x - points[i].x;
int g = std::gcd(std::abs(dy), std::abs(dx));
dy /= g;
dx /= g;
mp[{dx, dy}].push_back({i, j});
}
}
int ans = 0;
for (const auto& [vec, pairs] : mp) {
int dx = vec.first;
int dy = vec.second;
if (pairs.size() < 2) continue;
std::vector<Event> events;
std::vector<int> coords;
events.reserve(2 * pairs.size());
coords.reserve(2 * pairs.size());
for (const auto& pp : pairs) {
Point p1 = points[pp.first];
Point p2 = points[pp.second];
int nx = p1.x * dy - p1.y * dx;
int ny1 = p1.x * dx + p1.y * dy;
int ny2 = p2.x * dx + p2.y * dy;
events.push_back({false, {nx, ny1}});
events.push_back({true, {nx, ny2}});
coords.push_back(ny1);
coords.push_back(ny2);
}
std::sort(coords.begin(), coords.end());
coords.erase(std::unique(coords.begin(), coords.end()), coords.end());
auto get_comp = [&](int val) { return std::lower_bound(coords.begin(), coords.end(), val) - coords.begin() + 1; };
for (auto& e : events) {
e.p.y = get_comp(e.p.y);
}
std::sort(events.begin(), events.end(), [](const Event& a, const Event& b) { return a.p.x < b.p.x; });
int D = coords.size() + 2;
seg_tree::build(1, 1, D);
int i = 0;
int ev_size = events.size();
while (i < ev_size) {
int j = i;
while (j < ev_size && events[j].p.x == events[i].p.x) {
j++;
}
for (int k = i; k < j; k++) {
if (!events[k].isEnd) {
int L_curr = events[k].p.y;
int total_in_tree = seg_tree::d[1];
int smaller_equal = seg_tree::query(1, 1, D, 1, L_curr);
ans += (total_in_tree - smaller_equal);
}
}
for (int k = i; k < j; k++) {
if (events[k].isEnd) {
int R_curr = events[k].p.y;
seg_tree::update(1, 1, D, R_curr);
}
}
i = j;
}
}
std::cout << ans << '\n';
}
int32_t main() {
#ifndef GARY_DBG
std::ios_base::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
#endif
int t = 1;
// std::cin >> t;
for (; t > 0; t--) {
solve();
}
return 0;
}