Sereja has painted n distinct points on the plane. The coordinates of each point are…
- User
Sereja has painted n distinct points on the plane. The coordinates of each point are integers. Now he is wondering: how many squares are there with sides parallel to the coordinate axes and with points painted in all its four vertexes? Help him, calculate this number. Input
The first line contains integer n (1 ≤ n ≤ 105). Each of the next n lines contains two integers xi, yi (0 ≤ xi, yi ≤ 105), the integers represent the coordinates of the i-th point. It is guaranteed that all the given points are distinct.
Output
In a single line print the required number of squares.
Examples
Input
5 0 0 0 2 2 0 2 2 1 1
Output
1
Input
9 0 0 1 1 2 2 0 1 1 0 0 2 2 0 1 2 2 1
Output
5
Assistant
We need to count number of axis-aligned squares (sides parallel to coordinate axes) such that all four corners are among the given points.
Points are distinct, coordinates up to 10^5, n up to 1e5.
We need to count squares: For each possible pair of points that could be opposite corners? Actually for axis-aligned squares, the sides are horizontal/vertical. So a square can be defined by its left-bottom corner (x, y) and side length s>0. Then corners: (x, y), (x+s, y), (x, y+s), (x+s, y+s). So we need all four points present.
Thus we need to count quadruples (x, y, s) such that these four points are in the set.
Brute force over all points as bottom-left corner and s would be too large.
We can use hashing of points: store points in a hash set (e.g., using Python set of tuples). Then we can iterate over each point, treat it as potential bottom-left corner? But then we need to find the other three corners. However, many squares will be counted multiple times (each square has four corners, so four choices of bottom-left if we assume orientation? But bottom-left is uniquely defined: it's the corner with smallest x and y among the four? Actually for axis-aligned square, the bottom-left is the one with minimum x and minimum y (assuming y coordinate increases upward). But careful: Usually coordinates given are arbitrary, but we can define: For square with corners (x1,y1), (x1+s, y1), (x1, y1+s), (x1+s, y1+s). If we treat bottom-left as (x_min, y_min) then indeed it's unique. So we can iterate over each point, treat it as potential bottom-left (x,y). But we need to consider possible side lengths s. For each (x,y), we can find s such that (x+s,y), (x,y+s), (x+s,y+s) are in the set. But s could be any positive integer, but we can't iterate over all possible s.
Alternative: iterate over pairs of points that could be opposite corners? For axis-aligned squares, opposite corners are (x,y) and (x+s, y+s) (bottom-left and top-right) OR (x, y+s) and (x+s, y) (top-left and bottom-right). Actually both pairs are opposite. So if we pick two points, they could be either bottom-left and top-right, or top-left and bottom-right. To be opposite corners of an axis-aligned square, their x and y coordinates must differ by the same absolute difference (i.e., the rectangle formed must be a square, meaning |x1-x2| = |y1-y2|). And then the other two corners are determined: For points (x1,y1) and (x2,y2) with x1 < x2 and y1 < y2 (assuming bottom-left and top-right), the other corners are (x1, y2) and (x2, y1). If y1 > y2, then it's top-left and bottom-right. So essentially, for any unordered pair of points with |dx| = |dy| ≠ 0, we can consider them as opposite corners, then check if the other two corners exist. If they do, that forms a square. But each square will be counted twice? Let's see: a square has two diagonals. The two opposite corners along one diagonal form a pair; the other diagonal forms another pair. So each square has two pairs of opposite corners. So if we count all unordered pairs of points with equal |dx|=|dy| and then check existence of the other two points, we would count each square twice (once for each diagonal). To avoid double counting, we can divide by 2 at the end. But careful: When we have two points with dx = dy = s (or dx = -dy), but we require that they are opposite corners? Actually for an axis-aligned square, opposite corners have coordinates (x, y) and (x+s, y+s) OR (x, y+s) and (x+s, y). So in both cases, the absolute differences in x and y are equal: |dx| = |dy| = s. But the signs may differ: For bottom-left and top-right, dx>0, dy>0. For top-left and bottom-right, dx>0, dy<0 (or dx<0, dy>0). So indeed any pair with |dx| = |dy| > 0 could be opposite corners. However, not all such pairs are opposite corners; they could be other diagonal? Actually any two points with |dx| = |dy| can be the opposite corners of a square? Let's check: Suppose we have points (0,0) and (2,2). They can be opposite corners of square with corners (0,0),(2,0),(0,2),(2,2). For points (0,2) and (2,0) also satisfy |dx|=|dy|=2 and they are opposite corners of same square. So indeed both pairs are valid. So if we check each unordered pair with |dx|=|dy|, and if the other two corners exist, we count the square. But each square will be counted twice (once for each diagonal). So total number of squares = count / 2.
But we must be careful not to count squares with zero side length? Points distinct, so s>0.
Thus algorithm: Put all points in a set (e.g., Python set of tuples). Then iterate over all unordered pairs of points? That's O(n^2) which is too large for n=1e5.
We need a smarter approach. Since coordinates up to 10^5, we could maybe sort points and consider bounds? Another approach: For each possible side length s? Not efficient.
Maybe we can bucket points by x coordinate or y coordinate. But still O(n^2) worst-case.
We can think of counting squares via enumerating one corner and side length, but using hashing to check existence. The number of possible side lengths can be up to 10^5, but if we iterate over points and for each point consider other points with same x or y? Not directly.
Alternate method: For each point as bottom-left, we can find potential other points on same horizontal line (same y) and vertical line (same x). For a given bottom-left (x,y), if we have a point (x+s,y) and (x,y+s) in the set, then we need (x+s, y+s) to complete. So we can for each point, consider all points with same y (rightwards) and with same x (upwards). But that still may be O(n^2) if many points share same coordinate.
But note: Coordinates up to 1e5, n up to 1e5. In worst case, points could be all on a single line? But then squares can't exist because need distinct y for vertical sides. However, there could be many points sharing same x or y. For instance, all points on grid points of a 1e5 by 1e5 region but sparse? Actually worst-case for algorithm: Suppose we have points on a rectangular grid of size sqrt(n) by sqrt(n)? But n=1e5, so grid of about 316 x 316. Then many points share x or y, but not too many? Actually if we have points on all integer coordinates in a sqrt(n) by sqrt(n) area, then each row has sqrt(n) points. For a given bottom-left, there can be up to sqrt(n) points to the right and up to sqrt(n) points upwards, leading to O(n * sqrt(n)) = 1e5 * 316 = 3e7, maybe borderline but perhaps acceptable in Python with optimizations? But not guaranteed: coordinates up to 1e5, but n could be 1e5, and we could have points on many different x and y, but still each point might have few neighbors on same row/column.
Worst-case for such approach: Suppose we place half of points on a vertical line (same x) and half on a horizontal line (same y). But then for points on vertical line, they share same x, but many different y. For a bottom-left point on the horizontal line? But bottom-left must have both right and up neighbors. If many points on a horizontal line, then for a point on that line, there could be many rightwards neighbors. For example, take n/2 points on the line y=0 with various x, and n/2 points on the line x=0 with various y. Then a point at (0,0) is both on horizontal and vertical. For (0,0) as bottom-left, rightwards neighbors: all points on y=0 with x>0, count ~ n/2, and upwards neighbors: all points on x=0 with y>0, count ~ n/2. Then we would consider O((n/2)*(n/2)) = O(n^2/4) pairs, too large.
But we can avoid that by using a different method: count squares by diagonal pairs. That also would be O(n^2) if we consider all pairs.
Thus we need a more clever counting.
Observation: For axis-aligned squares, the four corners have coordinates (x, y), (x+s, y), (x, y+s), (x+s, y+s). So given bottom-left and top-right (or top-left and bottom-right) we can determine. Could we use coordinate compression and bitsets? Possibly but with up to 1e5 coordinates each up to 1e5, we could create a grid with bitsets but that would be 1e5 x 1e5 too large.
Alternate approach: Since coordinates are up to 10^5, we can use a 2D boolean array of size (10^5+1)^2? That's 10^10, impossible.
We need to use hashing and efficient enumeration.
Maybe we can consider squares by side length s: For each possible s, the number of squares of side length s is something like: For each point (x,y) that could be bottom-left, check existence of the other three. But s could be up to 1e5, and n up to 1e5. If we iterate over all points and all s, too many.
But perhaps the number of squares is limited? In worst-case, if we have all points on a grid of size M x M (M up to 1e5), then the number of possible squares is about M^2? Actually in a dense grid of points, the number of axis-aligned squares with integer vertices is about (M-1)^2 for size 1? For each possible bottom-left (x,y) with x from 0..M-1-s, y similar. That's O(M^2) which could be up to 1e10. But given n is only 1e5, we cannot have that many points; the grid is sparse. The maximum number of squares we can have given n points is limited. Perhaps we can aim for an algorithm that is output-sensitive: O(n sqrt(n)) or something.
Consider that each square is determined by its diagonal. If we enumerate all pairs of points (i,j) such that |dx| = |dy|, and check other two points, that would be O(n^2) in worst case. However, is it possible to have many pairs with |dx| = |dy|? Let's think. For a set of n points, the number of pairs with equal absolute difference could be large. In a grid of points on a line x-y = constant? Actually points on a line with slope 1: For any two points on such line, dx=dy. If we have many points on a 45-degree line, then many pairs satisfy dx=dy. For example, take points (i,i) for i=1..n. Then any pair has |dx|=|dy|. That's O(n^2) pairs. But in such case, can those pairs form squares? For two points (a,a) and (b,b) with a<b, the other two corners would be (a,b) and (b,a). Unless (a,b) and (b,a) are also in the set, they won't form a square. Since our set only contains points on the line y=x, the other two corners are off the line, so they are not present. So squares would be few. However, we might waste time checking many pairs that yield no square. So we need to avoid enumerating all such pairs.
We could try to enumerate squares by the side length and using data structures to quickly find points with given x and y. For each point, we could look for points with same x (vertical neighbors) and same y (horizontal neighbors) and then for each such pair that forms a potential square? Wait: Another way: For each potential horizontal segment (two points with same y and x1 < x2), that gives a side length s = x2 - x1. Then the square would have that as bottom side (or top side) if the corresponding vertical sides exist. Specifically, if we have two points (x1, y) and (x2, y) with x2 - x1 = s > 0, then the square could have this as bottom side: we need points (x1, y+s) and (x2, y+s) to exist. Or as top side: need (x1, y-s) and (x2, y-s). So for each horizontal pair (same y), we can check for the existence of the two points shifted by ±s in y direction. Similarly using vertical pairs.
If we enumerate all pairs of points with same y, that could be many: if many points share same y, worst-case O(n^2) (like all points on a horizontal line). But again, in that case squares are unlikely because we need vertical points. However, we might still have many pairs to check.
Maybe we can restrict enumeration to points that are "close" in some sense? But worst-case might still be large.
We could use a divide-and-conquer approach based on x-coordinate? Or use bitset? Possibly we can sort points by x, then for each x, we have list of y's. But still.
Another idea: Since coordinates are limited to 0..1e5, we could use a 2D array of bitsets for each x or y using Python's integers as bitsets? For each x coordinate, we can have a bitset of size (maxY+1) indicating which y's are present. That would be memory: (1e5+1) * (1e5+1/8) bits = about 1e5 * 1e5 / 8 = 1.25e9 bytes, too big. Not feasible.
But maybe we can compress y's per x: store set of y for each x (dictionary). Similarly store set of x for each y. That's typical: points_by_x = defaultdict(set) and points_by_y = defaultdict(set). This uses O(n) storage.
Now, we can try to count squares efficiently by iterating over possible side lengths? Not directly.
Consider enumerating the square by its bottom-left corner (x,y). For a given bottom-left, we need to check existence of (x+s, y) and (x, y+s). So if we have points_by_y[y] contains x+s, and points_by_x[x] contains y+s, then we need (x+s, y+s). So we need to iterate over each point (x,y) and for each possible s from neighbor x coordinates on row y and neighbor y coordinates on column x. This is like for each point, we intersect the set of x-coordinates greater than x in row y, and y-coordinates greater than y in column x, and for each such s, check if (x+s, y+s) exists. This is essentially considering all pairs (x1,y) and (x,y1) where x1 > x and y1 > y, and if x1 - x = y1 - y = s, then we have a square if (x1,y1) exists. So we are looking for pairs of points: one on the same horizontal line to the right, one on the same vertical line above, such that the horizontal and vertical distances are equal. Then check the diagonal point.
This is similar to enumerating pairs of points that share the same x or y with the base point.
One approach: For each point (x,y), we can iterate over the smaller of the two neighbor sets: for each possible x' > x in row y, compute s = x' - x, then check if y+s in column x and check (x', y+s). Or for each y' > y in column x, compute s = y' - y, then check if x+s in row y and check (x+s, y'). To avoid double counting squares? If we use bottom-left as anchor, each square counted exactly once. So this enumeration would be fine if we can process each point efficiently.
Now, the complexity depends on the sizes of neighbor sets. In worst-case, a point could have many neighbors on its row and column. As earlier, consider a configuration with many points on the same row and many on the same column. For point at intersection (0,0), the row has many points (x_i,0) and column has many points (0,y_j). Then the number of potential pairs is O(deg_row * deg_col). If deg_row and deg_col are both O(n), then O(n^2). But maybe we can handle such case by always iterating over the smaller set? That is, for each point, we can decide to iterate over the set of horizontal neighbors or vertical neighbors, whichever is smaller. However, for the intersection point (0,0), both sets could be large (up to n/2 each). But if we iterate over the smaller set, it's still up to n/2 if both are n/2? Actually smaller would be n/2 as well, so still O(n^2) worst-case if many points lie on two perpendicular lines.
But maybe such configuration yields few squares? Let's analyze: if many points are on the line y=0 (horizontal) and x=0 (vertical), then the only possible squares would need bottom-left at (0,0) and need (s,0) and (0,s) present, and (s,s) present. For a square to exist, we need point (s,s) present. In this configuration, we have points on axes only (x,0) and (0,y). So (s,s) would be missing unless we also include diagonal points. So squares are unlikely, so we can early exit? But the algorithm would still check many pairs, causing TLE.
We need a method that avoids O(n^2) in all cases, perhaps by using hashing and clever enumeration that counts squares without scanning all pairs.
Alternative idea: For each possible side length s, consider all points that could be bottom-left such that (x, y) and (x+s, y) and (x, y+s) exist. That is essentially: for each y, consider points with coordinates (x, y) and (x+s, y) both present; that is a horizontal segment of length s. For each such segment, we need a vertical segment of length s starting from (x, y) and from (x+s, y) to form the square. So we can group horizontal edges by y and s. For each y, we can have a list of x such that both (x, y) and (x+s, y) are present. That is like for each y, for each point (x,y) we check if (x+s, y) exists. That can be done by scanning sorted x list for that y: for each x, we can look for x+s. This yields for each y and s, a set of left x where horizontal edge exists. Similarly, for each x, we can have vertical edges: (x, y) and (x, y+s) exist.
Now a square of side s with bottom-left (x,y) exists if there is a horizontal edge from (x,y) to (x+s,y) and a vertical edge from (x,y) to (x,y+s) and also the top horizontal edge (x, y+s)-(x+s,y+s) must exist? Actually if we have both the bottom edge and left edge, we still need the top-right corner (x+s, y+s). But if we have both bottom and left edges, we can check that point. Alternatively, if we have bottom edge and left edge, we can check the existence of (x+s, y+s). So we can count squares by iterating over all horizontal edges (of length s) and for each, check if the corresponding left vertical edge exists and the diagonal point exists.
But enumerating all horizontal edges could be many: For a row with m points, the number of pairs (x, x+s) for various s could be O(m^2) in worst case if points are dense. But m could be up to n in worst case (all points on same row). However, in that case, horizontal edges exist for many s, but squares unlikely because vertical edges missing. But still enumeration cost is high.
But maybe we can bound total number of horizontal edges across all rows? For a set of n points, the total number of pairs of points sharing the same y coordinate is sum over y of C(m_y, 2), where m_y is number of points with that y. This sum could be as high as O(n^2) if points are concentrated on few rows. For example, all points on one row yields C(n,2) pairs ~ n^2/2. So enumerating all horizontal edges is O(n^2) in worst case.
Similarly vertical edges.
Thus we need a method that avoids enumerating all pairs of collinear points.
Maybe we can use a divide-and-conquer approach based on the difference between coordinates? Another thought: Because the squares are axis-aligned, we can map each point to its x and y. Consider that for each square, the four points form a "cycle" (x,y), (x+s,y), (x,y+s), (x+s,y+s). This is essentially a rectangle with equal sides.
Maybe we can treat points as a graph? Not helpful.
Could we use offline queries and range queries? For each potential bottom-left (x,y), we need to know whether (x+s,y) and (x,y+s) exist. Instead of iterating over s, we could for each point (x,y) query for existence of points that form a square with it, by intersecting the set of points with same y and greater x, and same x and greater y, but we can speed up by using data structures like balanced BST per row/column and doing something like two-pointer sweeps? But still, in worst case of many points on a row, scanning all right neighbors might be O(n^2). However, we could process rows and columns in a way that total work is O(n sqrt(n)) by splitting into heavy and light rows/columns.
That's a typical technique: For problems involving pairs of points on same row/col, we can classify rows as "heavy" if they contain more than B points, and "light" otherwise. Then for interactions between heavy rows and others, we handle differently.
We can apply this: We want to count squares. Each square is defined by bottom-left (x,y) and side s. It requires points: A=(x,y), B=(x+s,y), C=(x,y+s), D=(x+s, y+s). All four must exist.
We could enumerate squares by considering two points that share same x or same y. Perhaps we can iterate over pairs of points that are potential left side (vertical segment) or bottom side (horizontal segment), but using heavy-light.
Let's think: We can iterate over each possible s? Not.
Consider using the following: For each point (x,y), we can iterate over the "smaller" of the two neighbor sets (rightwards on same y, upwards on same x). To avoid O(n^2), we need to guarantee that total work is O(n sqrt(n)) or similar. The idea: For each point, if the number of points on its row is small, we can iterate over all right neighbors; if the number is large (heavy row), we instead iterate over points on its column, but only if the column is small, otherwise? Actually, we can use a threshold to decide which direction to iterate. But we need to avoid double counting squares and ensure each square is counted exactly once.
Specifically, for each potential square, we can count it when we consider the bottom-left corner. For bottom-left (x,y), we need to check right neighbor (x+s,y) and up neighbor (x,y+s). So we need to find s such that both exist and also (x+s,y+s) exists.
We can for each point (x,y) (as bottom-left), we need to consider pairs consisting of one point on same row to the right, and one point on same column above, with equal horizontal and vertical distances. That is like we need to intersect the set of distances (x' - x) from row-right neighbors and distances (y' - y) from column-up neighbors.
If we have sets R = {dx = x' - x | (x', y) in points, x' > x} and U = {dy = y' - y | (x, y') in points, y' > y}. We need dx = dy = s, and also (x+s, y+s) in points. So we need to find s in intersection of R and U, and then verify the diagonal.
We can compute the intersection efficiently if we iterate over the smaller of the two sets, and for each dx in R, check if (x, y+dx) in column? Actually we need to check if (x, y+dx) exists? Wait: we need dy = dx, so we need (x, y+dx) exists (that is the up neighbor) and also (x+dx, y+dx) exists. But if we iterate over dx from R, we can check: if (x, y+dx) is in the set (i.e., column contains y+dx), then we also check (x+dx, y+dx). That's a valid square. Similarly, iterating over dy from U.
Thus for each point (x,y), the work is min(|right_neighbors|, |up_neighbors|). But note: we need to consider only up neighbors where y' > y. Actually up_neighbors are points with same x and larger y. So sizes are deg_row_right(x,y) and deg_col_up(x,y). So total work across all points is sum over points of min(deg_row_right, deg_col_up). However, deg_row_right for a point is the number of points on same row with x' > x. Summing over all points, the sum of deg_row_right over all points equals total number of ordered pairs of points on same row with second point to the right? Actually for a given row with m points, sorted by x, the number of right neighbors for each point is (m-1-i) for i from 0 to m-1, sum = C(m,2). So sum over points of deg_row_right = total number of unordered pairs on same row? Actually it's sum of (m-1-i) which is C(m,2). So sum of deg_row_right across all points = total number of ordered pairs (i,j) with i<j on same row. That's total horizontal pairs (ordered by increasing x). That's O(n^2) in worst case if all points on same row. Similarly, deg_col_up sum = total vertical pairs (ordered by increasing y). Also O(n^2) in worst case if all points on same column.
But we are not summing the deg itself; we are summing min(deg_row_right, deg_col_up). This could still be large in worst case? Consider all points on a single row: then for each point, deg_row_right could be O(n), but deg_col_up is 0 (since no points above). So min = 0, sum = 0. Good. Consider all points on a single column: similarly sum min = 0. Consider half points on row y=0, half on column x=0, and also points at (i,i) for i from 1..k? Let's craft a worst-case where both deg_row_right and deg_col_up are large for many points. For points on the intersection of a dense row and a dense column. For instance, suppose we have a full grid of size m x m, with n = m^2. In such grid, each point has deg_row_right = m - (index+1) ~ up to m, deg_col_up similar. So min would be about m/2? Actually average deg_row_right per point in a row is (m-1)/2. So for each point, min is about (m-1)/2. There are m^2 points, so sum of min ~ m^2 * m/2 = O(m^3) = O(n^(3/2)). Because n = m^2, m = sqrt(n), so m^3 = n^(3/2). That's about 1e5^(1.5)= 3.16e7, which might be acceptable. Indeed, O(n^(3/2)) is often acceptable for n=1e5 (around 30 million operations). However, in a full grid, n = 1e5 would imply m = sqrt(1e5) ≈ 316, so m^3 = 31.6 million. That's okay.
But is this the worst-case scenario? We need to consider sets of points that are not full grid but where many points have both many right neighbors and many up neighbors. That would require many points sharing the same row and also many points sharing the same column. The worst case for sum of min might be when we have a balanced bipartite-like structure: Many rows and columns each with many points, and many points at intersections. The extreme is a complete bipartite between a set of rows and columns? But points exist only at intersections where specific x and y are present. So suppose we have R rows (y values) and C columns (x values), and we place points at all intersections (i.e., a full R x C grid). Then n = R*C. For each point, deg_row_right = C - 1 (since row has C points), deg_col_up = R - 1? Actually up neighbors: points with same x and larger y. In a grid, each column has R points, so number of points above = R - (row index) - 1. But averaged over all points, the average deg_col_up = (R-1)/2. But min(deg_row_right, deg_col_up) for a point is roughly min(C, R). In a grid, if R and C are balanced, min ~ sqrt(n). So sum of min over n points ~ n * sqrt(n) = n^(3/2). So the bound O(n^(3/2)) holds for any grid.
But can we construct a point set where sum of min is larger than O(n^(3/2))? Let's try to maximize sum of min given n points. For each point, deg_row_right is at most number of points on its row minus 1, and deg_col_up is at most number of points on its column minus 1. The sum over points of min(deg_row_right, deg_col_up) ≤ sum over points of sqrt(deg_row_right * deg_col_up) maybe? Not needed.
We can bound the total sum by O(n sqrt(n)) using heavy-light type argument. Actually we can prove that sum of min over all points is O(n sqrt(n)). Because consider all rows with many points: heavy rows have > sqrt(n) points. There are at most sqrt(n) such rows (since total points n). Similarly for heavy columns. Points that lie on both a heavy row and a heavy column are at most (number of heavy rows)*(number of heavy columns) ≤ sqrt(n)*sqrt(n) = n. For such points, min could be large (up to sqrt(n) maybe). So their contribution is at most n * sqrt(n) = n^(3/2). For points that are on a light row (≤ sqrt(n) points) or light column, then at least one of deg_row_right or deg_col_up is ≤ sqrt(n). So min ≤ sqrt(n). Since there are n points, total contribution ≤ n * sqrt(n) = n^(3/2). So indeed sum of min across points is O(n sqrt(n)). This is a standard trick.
Thus if we implement the algorithm: For each point (x,y) as bottom-left, we iterate over the smaller of the two neighbor sets (rightwards on same row, or upwards on same column). For each candidate s from the smaller set, we check if the other two corners exist. That would have total work O(n sqrt(n)) in the worst case, which is feasible for n=1e5 (around 3e7 checks). Each check involves set lookups (O(1) average). So this should be okay.
We need to be careful to count each square exactly once. Our loop for each point as bottom-left will count each square exactly once because bottom-left is unique: it's the corner with smallest x and y among the four. However, note: what about squares where sides are oriented such that bottom-left is not necessarily the point with smallest x and y? For axis-aligned squares, bottom-left is indeed the point with minimum x and minimum y among the four. But if we consider all points, we can treat each point as candidate bottom-left only if we ensure that we only consider s>0 and we only look at rightwards and upwards neighbors. That ensures we count each square exactly once. However, we must be careful: Could there be squares where two points share the same minimum x? No. So it's fine.
Thus algorithm:
- Input n, points.
- Store points in a set for O(1) membership checks.
- Also store points_by_x: mapping x -> sorted list of y's (or set) for points with that x. For each column x, we need to know y's above a given y (greater y). Similarly, store points_by_y: mapping y -> sorted list of x's for points with that y. For each row y, we need to know x's to the right (greater x). To efficiently iterate over rightwards neighbors of (x,y), we can for a given row y, have the list of x coordinates sorted. Then for a point (x,y) we can consider all x' in that list that are > x. However, iterating over all such x' might be inefficient if we just iterate over entire tail. But we only need to iterate over the smaller of the two sets (rightwards vs upwards). So we can for each point, get the list of x's for its row and list of y's for its column. We need to extract the suffix (greater than current) for each. We could for each point, if the number of points to the right on its row is less than the number of points above on its column, we iterate over those x' values; else we iterate over y' values.
But we need to be able to iterate over the elements greater than current in sorted order. Since we have the lists sorted, we can for each point, find its index in the list (by binary search) and then iterate over the remaining elements. However, if we do binary search for each point, that adds log factor, but okay.
Implementation steps:
-
Read points, store in set
pts = set((x,y)). -
Build dictionary
row = defaultdict(list)where key = y, value = sorted list of x coordinates of points with that y. -
Build dictionary
col = defaultdict(list)where key = x, value = sorted list of y coordinates of points with that x.- Since we need to iterate over points for each row/col, we can just append then sort each list.
-
Initialize count = 0.
-
For each point (x,y) in pts:
- Get list_x = row[y] (sorted). Find position i such that list_x[i] == x (or using binary search to find index). We need the rightwards part: list_x[i+1:] (all x' > x). Let right_count = len(list_x) - i - 1.
- Get list_y = col[x] (sorted). Find position j such that list_y[j] == y. Upwards part: list_y[j+1:] (all y' > y). Let up_count = len(list_y) - j - 1.
- Choose the smaller side for iteration: if right_count <= up_count, we iterate over x' in list_x[i+1:].
For each x' in that suffix:
s = x' - x
Check if (x, y+s) exists (i.e., if (x, y+s) in pts). Since we have col[x] list, we could check quickly: we could binary search in col[x] to see if y+s exists. But we are already iterating over rightwards, so we need to check if the point (x, y+s) is present, and if (x', y+s) is present. However, note that (x, y+s) is the top-left corner? Actually for bottom-left (x,y), with right neighbor (x',y), we need s = x' - x, then we need (x, y+s) and (x', y+s). So we check:
if (x, y+s) in pts and (x', y+s) in pts: count += 1.
Since we have
ptsset, membership is O(1). So we can simply do two set lookups. - Else (up_count smaller), iterate over y' in list_y[j+1:]: s = y' - y Check if (x+s, y) in pts and (x+s, y') in pts: count += 1.
-
At the end, output count.
This will count each square exactly once because we only count when considering bottom-left and s>0. But wait: Could there be squares where bottom-left point is not the one with smallest x and y? Actually for an axis-aligned square, the bottom-left is indeed the point with smallest x and smallest y. But what if we have a square oriented differently? All squares are axis-aligned, so that holds. So we are good.
Double-check: Consider square with corners (0,0), (2,0), (0,2), (2,2). Bottom-left is (0,0). Our algorithm when processing (0,0) will iterate over rightwards (2,0) or upwards (0,2). Suppose we choose smaller set (both size 1). If we iterate over rightwards (2,0): s=2, check (0,2) and (2,2) exist -> count++. When processing other points, they might also qualify? (0,2) as bottom-left? Its y is 2, but there is no point with y>2? So no. (2,0) as bottom-left? x=2, no point with x>2? No. (2,2) as bottom-left? no. So counted once.
Consider square with side length zero? Not allowed as points distinct.
Now, is there any risk of counting squares where bottom-left point has multiple rightwards neighbors that yield same s? That's fine, each s defines different square.
Now, complexity: For each point, we need to find its index in row[y] and col[x]. We can precompute positions? Since we need to iterate over suffixes, we could for each point, retrieve the list and binary search for its index each time. That's O(log n) per point, overall O(n log n). That's fine. Alternatively, we could pre-sort the lists and then for each point store its index? But easier to binary search.
However, we need to ensure that when iterating over the suffix, we don't incur overhead of creating new lists (slicing) which copies. Instead we can get the index and then iterate from index+1 to end using a for loop over the original list.
So algorithm steps:
-
Read points.
-
Build row dict: for each point, row[y].append(x). Then after reading, for each y, sort row[y].
-
Build col dict: col[x].append(y). Then sort each.
-
For each point (x,y):
-
xs = row[y]; find idx_x = bisect_left(xs, x) (should find exact, but since x is present, we can also use index? but bisect works).
-
right_count = len(xs) - idx_x - 1
-
ys = col[x]; idx_y = bisect_left(ys, y)
-
up_count = len(ys) - idx_y - 1
-
if right_count <= up_count: for i in range(idx_x+1, len(xs)): x2 = xs[i] s = x2 - x if (x, y+s) in pts and (x2, y+s) in pts: count += 1 else: for i in range(idx_y+1, len(ys)): y2 = ys[i] s = y2 - y if (x+s, y) in pts and (x+s, y2) in pts: count += 1
-
Edge Cases: Ensure that s > 0 automatically because we only consider points to right/up.
Potential double counting? We only consider bottom-left, so each square counted once. But need to ensure that we are only counting squares where (x, y+s) and (x+s, y+s) exist. However, what if the square is not oriented with bottom-left as defined? Could there be a square where the point we treat as bottom-left is not the one with smallest x and y because we might have points with same x or y? Actually, for a square, all four x coordinates are two distinct values: x and x+s, similarly y and y+s. So there is a unique point with smallest x and smallest y (since points are distinct). So that's the bottom-left. So our condition of iterating over rightwards and upwards from that point is correct.
But what about squares where the point we are considering is bottom-left but we may have both right and up neighbors, but we only iterate over the smaller set. That's fine because we still check both needed corners. In the case where we iterate over rightwards, we check for each x2 if (x, y+s) and (x2, y+s) exist. That's sufficient because we only need s = x2-x, and we verify the up neighbor (x, y+s) exists. However, note that it's possible that (x, y+s) exists but we might not have (x2, y+s) exist, so no square. That's correct.
Similarly, when iterating over upwards, we check (x+s, y) and (x+s, y2). That covers all squares.
Now, is it possible that we miss squares because the bottom-left point has both right and up neighbors but we choose to iterate over rightwards, but for some s, the up neighbor (x, y+s) does not exist, but there might still be a square if we had iterated over upwards? No: For a square, both (x+s, y) and (x, y+s) must exist. So if we iterate over rightwards, we check existence of (x, y+s) as part of condition. So we are still checking all s that correspond to rightwards neighbors. But if we only iterate over rightwards, we might miss squares where the rightwards neighbor (x+s,y) does not exist but the upwards neighbor (x, y+s) exists? However, for a square to exist, both must exist. So if rightwards neighbor doesn't exist, then there is no square with bottom-left (x,y) and that s (since bottom side missing). So we only need to consider s that correspond to either an existing rightwards neighbor or an existing upwards neighbor? Actually s must satisfy both: there is a point at (x+s, y) and a point at (x, y+s). So if we iterate over rightwards neighbors, we are checking s from those existing rightwards neighbors, and then verifying the existence of the up neighbor. That covers all s for which both exist because if both exist, then s will be in the set of rightwards neighbors (since (x+s,y) exists) and also in the set of upwards neighbors. So we could also choose to iterate over upwards and would also catch it. So by iterating over the smaller of the two sets, we still cover all s because if both exist, s appears in both sets. However, is it guaranteed that if both (x+s,y) and (x,y+s) exist, then (x+s,y) is a rightwards neighbor? Yes, because x+s > x (since s>0) and same y, so it's in the rightwards list. Similarly, (x,y+s) is in the upwards list. So s is in both sets. Therefore, by iterating over the smaller set, we will still examine that s when we loop through its elements, because we loop over all elements of that set. So we will catch all squares. There's no risk of missing squares because we only iterate over one set, but we loop over all its elements. Since s is in both sets, it is in the smaller set as well? Not necessarily: If rightwards set is smaller, s is in it because it's in rightwards set? Actually s is in the rightwards set because (x+s,y) exists. But what if the rightwards set is smaller? Then we iterate over rightwards set and we will see s. If the upwards set is smaller, we iterate over upwards and s is in it. So either way, s will be in the set we iterate over. Because s belongs to both sets. However, it's possible that the smaller set does not contain s? That can't happen because s belongs to both sets, so it belongs to the intersection. The intersection is a subset of both sets. So s is definitely in the smaller set because the smaller set is one of the sets. So we will iterate over s regardless of which set we pick, as long as we iterate over all elements of that set. Since we loop over all elements of the chosen set, we will encounter s. So all squares will be counted.
But careful: Suppose we choose to iterate over rightwards set because right_count <= up_count. In that loop, for each x2 we compute s = x2 - x. For a square to exist, we need (x, y+s) exist. But we also need to check (x2, y+s) exist. Our check includes both. So it's correct. However, what if the square exists but the rightwards set is smaller and we loop over it, we will encounter x2 = x+s. Then we check (x, y+s) and (x+s, y+s). That works.
Thus algorithm correctly counts each square exactly once.
Now, we need to ensure that for each point we consider as bottom-left, we only count squares where that point is indeed bottom-left. But what about squares where the bottom-left point is not present? That's impossible because all four corners must be present.
Now, complexity: For each point, we perform either loop over rightwards neighbors or upwards neighbors, whichever is smaller. As argued, total work is O(n sqrt(n)). Implementation details: We need to be able to get the list of xs for a given y, and for a given x, list of ys. We'll store them as lists (sorted). We also need to find index of the point in its row list and column list. We can use bisect from python's bisect module. Since the lists are sorted, bisect_left is O(log m). So overall O(n log n + total iterations). With n=1e5, total iterations up to ~3e7, which might be okay in Python if optimized (using local variables, avoid function calls, use set membership, etc.). However, we need to be careful about potential high constant factors. But 3e7 set lookups might be borderline but likely okay given typical time limits (2 seconds? Usually Codeforces problems have 2 sec; 3e7 operations might be too slow in Python if not optimized. But we can try to reduce constant.
We can also use an alternative: precompute for each point the index in row and column to avoid binary search. Since we have the lists, we could for each row, after sorting, create a dictionary mapping x to its index for quick lookup. But that would use extra memory O(n) which is fine. However, constructing such mapping for all rows could be done: For each y, after sorting xs, we can create a dict
row_index[y] = {x: idx for idx, x in enumerate(xs)}. Similarly for columns. This would allow O(1) index retrieval instead of O(log m). But building these dicts might cost O(total points) per row, which is O(n) total because sum of lengths of rows is n. So we can precompute index mapping.Alternatively, we can store for each point its position in the row list and column list while reading? Since we will build row and col lists after reading all points, we can then iterate over points again and find indices via binary search or via mapping. Using mapping might be faster.
Let's consider memory: For each point, we could store row index and col index directly as attributes. But we'd need to compute them after sorting. Could just use binary search; log factor is small (log up to 1e5 ~17). 1e5 * 2 * 17 = 3.4 million operations, negligible. So binary search is fine.
The heavy part is the loops over neighbor sets. To make it fast, we should use local variables and avoid attribute lookups. Use
pts_setas a set of integers (maybe encode (x,y) as a single integer like x * (MAX+1) + y) to speed up membership? Possibly, but tuple hashing is fine. But we can encode as (x << 20) | y since coordinates up to 1e5 (< 2^17). Shift by 17 bits? Actually 1e5 < 2^17=131072, so we can encode as x * 131072 + y, or x*100001 + y. Using integer may be faster. But set of tuples is usually okay. However, for 3e7 lookups, the hashing cost could be significant. Using integer encoding might reduce overhead. We'll consider encoding.Also, we need to ensure we don't double count due to squares that have side length zero? No.
Potential pitfalls: Coordinates up to 1e5, s could be up to 1e5. But fine.
Now, verify with examples:
Example1: 5 points: (0,0),(0,2),(2,0),(2,2),(1,1) Our algorithm:
- For (0,0): row[0]: xs = [0,2]; idx_x=0; right_count=1; col[0]: ys=[0,2]; idx_y=0; up_count=1; choose right (since equal). Loop over x2=2: s=2; check (0,2) in pts? yes; (2,2) in pts? yes; count=1.
- For other points: (0,2): row[2]: xs=[0,2]; idx_x=0; right_count=1; col[0]: ys=[0,2]; idx_y=1 (since y=2, index 1); up_count=0; choose right? right_count=1, up_count=0, min is up_count=0? Actually we compare right_count <= up_count? right_count=1, up_count=0 => right_count <= up_count is false, so we go else (up side). up_count=0, so loop over no y' (since idx_y+1 beyond end). So no addition.
- (2,0): similarly no squares.
- (2,2): up_count=0, right_count=0.
- (1,1): row[1]: xs=[1]; idx=0, right_count=0; col[1]: ys=[1]; up_count=0. Result=1.
Example2: 9 points: all combos from 0,1,2? Actually points: (0,0),(1,1),(2,2),(0,1),(1,0),(0,2),(2,0),(1,2),(2,1). That's all points in 3x3 grid. Number of axis-aligned squares? For a 3x3 grid (coordinates 0,1,2), squares of side length 1: bottom-left can be (0,0), (0,1), (1,0), (1,1) -> 4 squares. Side length 2: bottom-left (0,0) only -> 1 square. Total 5. So output 5.
Our algorithm should count 5.
Let's simulate: For each bottom-left point:
- (0,0): row0 xs [0,1,2]; idx0, right_count=2; col0 ys [0,1,2]; up_count=2; choose right (since <=). Iterate x2=1: s=1; check (0,1) and (1,1): both exist? (0,1) yes, (1,1) yes -> count 1. x2=2: s=2; check (0,2) and (2,2): both exist -> count 2. So adds 2? Actually squares: side 1 and side 2. So 2 squares counted from (0,0).
- (0,1): row1 xs [0,1,2]; idx for x=0? row1 xs = [0,1,2] (since points (0,1),(1,1),(2,1) all present). So idx_x=0, right_count=2; col0 ys [0,1,2]; idx_y for y=1 is 1; up_count=1 (since ys after index1: [2]). right_count=2, up_count=1, up_count smaller? Actually we compare right_count <= up_count? 2 <= 1 false, so we go else (iterate upwards). Then iterate over y' in col[0] from index1+1=2: y'=2; s=1; check (0+1,1) = (1,1) and (1,2)? Actually condition: check (x+s, y) and (x+s, y'). x=0, y=1, s=1: (1,1) exists, (1,2) exists? (1,2) is present. So count 1. That's the square with bottom-left (0,1) side 1? Actually square with bottom-left (0,1) would have corners (0,1),(1,1),(0,2),(1,2). That's a square of side 1. So adds 1.
- (0,2): row2 xs [0,1,2]; idx_x=0, right_count=2; col0 ys [0,1,2]; idx_y=2, up_count=0; right_count <= up_count? 2 <= 0 false -> else (up). up_count=0, so no iteration. But also consider bottom-left (0,2) would require points with y>2, none. So no squares.
- (1,0): col1 ys [0,1,2]; row0 xs [0,1,2]; For (1,0): row0 xs, idx for x=1 is 1, right_count=1 (x2=2); col1 ys, idx for y=0 is 0, up_count=2 (y'=1,2). right_count=1 <= up_count=2 true -> iterate over rightwards: x2=2; s=1; check (1,1) and (2,1)? (1,1) exists, (2,1) exists? (2,1) is present. So count 1. That's square with bottom-left (1,0) side 1: (1,0),(2,0),(1,1),(2,1) but we need (2,0) exists? Wait (2,0) is present. Our condition when iterating over rightwards from (1,0): we have x2=2 (right neighbor), we check (1,0+s) = (1,1) and (x2, 0+s) = (2,1). We didn't check (2,0) existence because it's the right neighbor itself (x2,0) we already know exists because we are iterating over rightwards neighbors from row0 list, so (2,0) is in the row list and thus present. So square is valid. So count 1.
- (1,1): row1 xs [0,1,2], idx_x=1 (x=1), right_count=1 (x2=