公式

B - Gentle Pairs 解説 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.

投稿日時:
最終更新: