Official

B - Gentle Pairs Editorial by en_translator


The slope of a line passing through two points \((a, b)\) and \((c, d)\) is defined by \(\frac{b-d}{a-c}\). (Since \(x\)-coordinates of \(N\) points are mutually distinct, you don’t have to worry about dividing by zero.)

Calculate the slope for every pair of points and count the number of slopes between \(-1\) and \(1\), then you will obtain AC.

Sample Code (C++)

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<pair<int, int>> A(N);
    for(auto& [x, y] : A) cin >> x >> y;
    int ans = 0;
    for(int i = 0; i < N; i++) for(int j = i + 1; j < N; j++){
        auto [x1, y1] = A[i];
        auto [x2, y2] = A[j];
        if(abs(y1 - y2) <= abs(x1 - x2)) ans++;
    }
    cout << ans << endl;
}

Sample Code (Python)

N = int(input())
A = [tuple(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
    for j in range(i):
        if abs(A[i][1] - A[j][1]) <= abs(A[i][0] - A[j][0]):
            ans += 1
print(ans)

BONUS : Try solving in a total of \(O(N \log N)\) time.

posted:
last update: