In [1]:
%%time
fin = open("7.in", "r")
fout = open("triangles.out", "w")
N = int(fin.readline().strip())
print("N",N)
keyX = dict()
keyY = dict()
points = []
xpointset = set()
ypointset = set()
for i in range(N):
X,Y = map(int,fin.readline().split())
xpointset.add(X)
ypointset.add(Y)
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
sumbaseX = dict() # use x,y as index
sumbaseY = dict() # use x,y as index
# compute sumbaseY and store for x and all y's in list
for x in xpointset:
n = len(keyX[x])
if n>1:
keyX[x].sort()
lasty=keyX[x][0]
lastsumy = sum([abs(a-lasty) for a in keyX[x]])
sumbaseY[(x,lasty)]=lastsumy
for i in range(1,n):
lastsumy = lastsumy + (2*i-n)*(keyX[x][i]-lasty)
lasty = keyX[x][i]
sumbaseY[(x,lasty)]=lastsumy
else:
for z in keyX[x]:
sumbaseY[(x,z)]=0
# compute sumbaseX and store for y and all x's in list
for y in ypointset:
n = len(keyY[y])
if n>1:
keyY[y].sort()
lastx=keyY[y][0]
lastsumx = sum([abs(b-lastx) for b in keyY[y]])
sumbaseX[(lastx,y)]=lastsumx
for i in range(1,n):
lastsumx = lastsumx + (2*i-n)*(keyY[y][i]-lastx)
lastx = keyY[y][i]
sumbaseX[(lastx,y)]=lastsumx
else:
for z in keyY[y]:
sumbaseX[(z,y)]=0
In [3]:
%%time
A=0
modval=1e9+7
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)
ans = int(A%modval)
print("ans",ans)
