← Real problems

cheerio1s3

easygeometryratiosStatement on DMOJ

CP Lang

11 lines0.3 spec
// cheerio1s3: count pairs p < q where q's slope from p ties the steepest or the shallowest
// slope from p seen so far. Slopes compare exactly as ratios, and "so far" is a running min
// and max over the points after p.
let n = read<1..=5_000>()
domain P = 1..=n
let pts = read<[P](x: Int, y: Int)>()
fn ties(p: P) -> Int:
    let s = pts[p.r..].map(q => Ratio(q.y - pts[p].y, q.x - pts[p].x))
    let (lo, hi) = (s.scan(min), s.scan(max))
    s.keys.count(q => s[q] == lo[q] or s[q] == hi[q])
print(P.map(ties).sum())

Accepted C++

71 lines · 0.39 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

bool cmp(pair<long, long> a, pair<long, long> b) {
    assert(a.second > 0 && b.second > 0);
    return a.first * b.second < a.second * b.first;
}

bool eq(pair<long, long> a, pair<long, long> b) {
    return !cmp(a, b) && !cmp(b, a);
}

void solve() {
    int n;
    cin >> n;
    int arr[n][2];
    for (auto& [x, y] : arr) {
        cin >> x >> y;
    }
    long ans = 0;
    for (int i = 0; i < n; i++) {
        auto& [x1, y1] = arr[i];
        pair<long, long> mx, mn;
        for (int j = i + 1; j < n; j++) {
            auto& [x2, y2] = arr[j];
            pair<long, long> cur {y2 - y1, x2 - x1};
            if (j == i + 1) {
                mx = mn = cur;
            }
            mn = min(mn, cur, cmp);
            mx = max(mx, cur, cmp);
            ans += eq(mx, cur) || eq(mn, cur);
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}