Submission #3494398

---

Source Code Expand

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
T = []
for i in range(1, 26):
    for j in range(1, 26):
        if gcd(i,j) == 1:
            T.append([i, j])

N = int(input())
L = [[0 for i in range(100)] for j in range(100)]
for i in range(N):
    x, y = map(int, input().split())
    L[x][y] = 1
h = 100
def exc(c):
    ret = 0
    if c >= 4:
        ret += (c*(c-1)*(c-2)*(c-3))//24
    if c>= 3:
        ret += ((c*(c-1)*(c-2))//6) * (N-c)
    return ret
ans = (N*(N-1)*(N-2)*(N-3))//24
for i in range(h):
    c=0
    for j in range(h):
        if L[i][j] > 0:
            c += 1
    ans -= exc(c)
for i in range(h):
    c=0
    for j in range(h):
        if L[j][i] > 0:
            c += 1
    ans -= exc(c)
for i, j in T:
    for a in range(i):
        for b in range(h):
            c = 0
            k = 0
            while True:
                if a + i*k >= h or b + j*k >= h:
                    break
                if L[a + i*k][b + j*k] > 0:
                    c += 1
                k += 1
            ans -= exc(c)
            
            c = 0
            k = 0
            while True:
                if a + i*k >= h or b - j*k < 0:
                    break
                if L[a + i*k][b - j*k] > 0:
                    c += 1
                k += 1
            ans -= exc(c)
    for a in range(i, h):
        for b in range(j):
            c = 0
            k = 0
            while True:
                if a + i*k >= h or b + j*k >= h:
                    break
                if L[a + i*k][b + j*k] > 0:
                    c += 1
                k += 1
            ans -= exc(c)
    for a in range(i, h):
        for b in range(h-j, h):
            c = 0
            k = 0
            while True:
                if a + i*k >= h or b - j*k < 0:
                    break
                if L[a + i*k][b - j*k] > 0:
                    c += 1
                k += 1
            ans -= exc(c)
    
print (ans)

Submission Info

Judge Result