13249번: 공의 충돌

https://www.acmicpc.net/problem/13249


$O(n^2)$


공이 부딛힌 후 그냥 지나간다고 생각하자.
떨어진 거리가 2t 이하인 임의의 한 쌍의 공은 1/4 확률로 충돌한다.

#include<cstdio>

int n, a[12], t, r;
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    scanf("%d", &t);
    for (int i = 0; i<n; i++)for (int j = i; j--;)r += a[i] <= a[j] + t * 2 & a[i] >= a[j] - t * 2;
    printf("%f", r / 4.0);
    return 0;
}