Manhattan Triangle
https://mirror.codeforces.com/contest/1979/problem/E
Given that the Manhattan distance between any two points is,
It's similar to adding two positive values whose sum is $$$d$$$. So, if we consider a point $$$(x,y)$$$ , then points that are at a distance $$$d$$$ from it are in the following form:
There could be more such sets of values if we consider adding $$$\pm d$$$ to $$$x$$$ or $$$y$$$.
If we look at the above set of points, all those points lie on a straight line with slopes $$$1$$$ and $$$-1$$$. This means considering a point $$$(x,y)$$$ , all the points that are at an equal Manhattan distance $$$d$$$ will form a square rotated by $$$45^\circ$$$ around it as a center.
Let's analyze this square, ABCD.
If we look at the square and select points A and B, then any point lying on the opposite side of the square CD will be at a Manhattan distance of $$$d$$$.
We will use this to solve the given problem.
If we transform the square by rotating it $$$45^\circ$$$ and scale it so that the sides become parallel to the axis, then all the vertical lines will reflect $$$x+y = d$$$ and all the horizontal lines will reflect $$$y-x = d$$$
Now, Lets consider
so each point can be represented as
Now, the line parallel to $$$X$$$ at a distance of $$$\pm d$$$ will be $$$X\pm d$$$, same goes with $$$Y$$$
Lets maintain three maps to represent the coordinates are their indexes,
type point struct {
x,y int
}
X := map[int][]int{}
Y := map[int][]int{}
imap := map[point]int{}
$$$X[i] =$$$ list of all $$$Y_j$$$ lying on the line $$$X = i$$$
$$$Y[i] =$$$ list of all $$$X_j$$$ lying on the line $$$Y = i$$$
$$$imap[{x,y}] =$$$ index of point $$$(x,y)$$$
Transform all Points
for p:=1 ; p<=n; p++ {
var pnt point
fmt.Scan(&pnt.x, &pnt.y)
temp := pnt.x
pnt.x = pnt.x + pnt.y
pnt.y = pnt.y - temp // y - x
imap[pnt] = p
X[pnt.x] = append(X[pnt.x], pnt.y) // x+y lines, vertical after rotation
Y[pnt.y] = append(Y[pnt.y], pnt.x) // x-y, horz
}
// sort to make the future search easier
for _,v := range X {sort.Ints(v)}
for _,v := range Y {sort.Ints(v)}
Check for Squares to select ABC
Lets start checking with left & right squares at the bottom formed with $$$Y-d$$$
For each point $$$(x,y)$$$ we need $$$(x,y-d)$$$ and a point between $$$[x+d, y , x+d,y-d]$$$
if _,there := imap[point{pnt.x, pnt.y - d}]; there {
// check for C
C_y := lower_bound(X[pnt.x+d], pnt.y-d)
if (C_y != nil && *C_y <= pnt.y) {
fmt.Println(imap[point{pnt.x, pnt.y}], imap[point{pnt.x, pnt.y-d}],imap[point{pnt.x+d, *C_y}]) // A
found = true
break
}
C_y = lower_bound(X[pnt.x-d], pnt.y-d)
if (C_y != nil && *C_y <= pnt.y) {
fmt.Println(imap[point{pnt.x, pnt.y}], imap[point{pnt.x, pnt.y-d}],imap[point{pnt.x-d, *C_y}]) // A
found = true; break;
}
}
We should also check for squares to the top i.e $$$Y+d$$$
if _,there := imap[point{pnt.x - d, pnt.y}]; there {
// check for C
C_x := lower_bound(Y[pnt.y+d], pnt.x-d)
if (C_x != nil && *C_x <= pnt.x) {
fmt.Println(imap[point{pnt.x, pnt.y}], imap[point{pnt.x-d, pnt.y}],imap[point{*C_x, pnt.y+d}])
found = true; break;
}
C_x = lower_bound(Y[pnt.y-d], pnt.x-d)
if (C_x != nil && *C_x <= pnt.x) {
fmt.Println(imap[point{pnt.x, pnt.y}], imap[point{pnt.x-d, pnt.y}],imap[point{*C_x, pnt.y-d}])
found = true; break;
}
}
And, We are done!!
Auto comment: topic has been updated by karthik.pasupulatei (previous revision, new revision, compare).
Nice one !! Clearly explained.