In [1]:
%%time
# Store all Y's with the same X in a dictionary with X as the key (keyX)
# Store all X's with the same Y in a dictionary with Y as the key (keyY)
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]
In [2]:
%%time
# for each point (x,y), find the area of all triangles with x,y as the right angle
A = 0
for x,y in points:
# consider triangles right angle at x,y
if len(keyX[x])>1 and len(keyY[y])>1:
for a in keyX[x]:
if a==y:
continue
for b in keyY[y]:
if b==x:
continue
A+=abs(a-y)*abs(b-x)
print("A",A)
print("ans",int(A%(1e9+7)))
WAY TOO SLOW. And there is something funny going on with the mod value.¶
In [3]:
# for reasons I don't understand, taking the mod with a float yields the correct answer
# but taking the mod with an integer yields the wrong answer
A=39999095165312717
modval1 = 1e9+7
modval2 = 1000000007
print("modval1",modval1)
print("modval2",modval2)
print("ans1",A%modval1)
print("ans2",A%modval2)
