Open Resry opened 7 years ago
struct frac {
int64_t top;
int64_t bot;
bool operator<(const frac& that) const {
return top * that.bot < bot * that.top;
}
bool operator==(const frac& that) const {
return top * that.bot == bot * that.top;
}
};
struct event {
int x, y;
frac when;
bool operator<(const event& that) const {
if (when == that.when) {
if (y != that.y)
return y > that.y;
return x > that.x;
}
return when < that.when;
}
};
vector<event> E;
E.reserve(N * N);
for (int i = 0; i < N; ++i)
for (int j = i + 1; j < N; ++j)
if (A[i].second != A[j].second)
E.emplace_back(event{i, j, frac{1LL * A[j].first * A[j].second - 1LL * A[i].first * A[i].second, A[i].second - A[j].second}});