USACO Triangles -- Version2

USACO 2020 February Contest, Silver¶

Problem 2. Triangles¶

http://usaco.org/index.php?page=viewproblem2&cpid=1015

In [1]:

%%time
fin = open("6.in", "r")
fout = open("triangles.out", "w")

N = int(fin.readline().strip())
print("N",N)

keyX = dict()
keyY = dict()
points = []

for i in range(N):
    X,Y = map(int,fin.readline().split())
    points.append((X,Y))
    if X in keyX:      
        keyX[X].append(Y)
    else:
        keyX[X]=[Y]
    if Y in keyY:
        keyY[Y].append(X)
    else:
        keyY[Y]=[X]

N 40000
Wall time: 130 ms

In [2]:

%%time
# for data set 6.in, this step takes 45.1 ms
# for data set 7.in, this step takes 1min 55s   TOO SLOW
sumbaseX = dict()
sumbaseY = dict()
for x,y in points:
    sumx = 0
    sumy = 0
    # consider triangles right angle at x,y 
    if len(keyX[x])>1 and len(keyY[y])>1:
        sumy = sum([abs(a-y) for a in keyX[x]])
        sumbaseY[(x,y)]=sumy                      # %(1e9+7)
        sumx = sum([abs(b-x) for b in keyY[y]])
        sumbaseX[(x,y)]=sumx                      # %(1e9+7)

Wall time: 45.1 ms

In [3]:

%%time
A=0
for x,y in points:
    if (x,y) in sumbaseY and (x,y) in sumbaseX:
        A+=sumbaseY[(x,y)]*sumbaseX[(x,y)]
    
print("A",A)    
print("ans",int(A%(1e9+7)))

A 39999095165312717
ans 885319062
Wall time: 9.88 ms