let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

QBPOINT - Bộ ba điểm thẳng hàng

solution.md

Duyệt \(k\) từ \(3\) đến \(N\), ta sẽ tìm số cặp \(i, j\) (\(1 \le i, j < k\)) sao cho \(P[i], P[j], P[k]\) thẳng hàng. Ta làm như sau:

  • Với mỗi \(i, 1 \le i < k\), tính \(\large A[i] = \frac{X[i] - X[k]}{Y[i] - Y[k]}\)
  • Đếm số lượng cặp \(i, j\) có \(A[i] = A[j]\) (sắp xếp lại A để đếm trong \(O(k)\)).

Độ phức tạp: \(O(N^2\log N)\).

main.cpp
Open in Github Download
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

ll solve(int k, const vector<double> &x, const vector<double> &y) {
    vector<double> a(k);
    for (int i=0; i<k; i++) {
        double dy = y[i] - y[k];
        if (dy != 0) a[i] = (x[i] - x[k]) / dy;
        else a[i] = 1e9;
    }
    sort(a.begin(), a.end());
    ll res = 0;
    ll count = 1;
    for (int i=1; i<k; i++) {
        if (a[i] != a[i-1]) {
            res += count*(count-1) / 2;
            count = 0;
        }
        count++;
    }
    res += count*(count-1) / 2;
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<double> x(n), y(n);
    for (int i=0; i<n; i++) cin >> x[i] >> y[i];
    ll res = 0;
    for (int i=2; i<n; i++) res += solve(i, x, y);
    cout << res;
    return 0;
}
Comments