You are given an array of points where each point has X and Y values. Find the midpoint of two points which exist in array in constant time.

class Point {

int x;

int y;

}

public List<Point> getMidPoint (Point[] list) {

// One way to find this to find midpoint of all points with each other and

// check if midpoint exist in array, but, that would be O(n^2).

}

I am wondering if it's possible to write Constant time solution for this.

This is the best I could think of:

private static List<IntPoint> findMidPoint(IntPoint[] array) {

```
List<IntPoint> result = new ArrayList<IntPoint>();
Map<Integer, Integer> mapper= new HashMap<Integer, Integer>();
for (int i = 0; i < array.length; i++)
mapper.put(array[i].X, array[i].Y);
for (int i = 0; i < array.length; i++) {
for(int j = i + 1; j < array.length; j++) {
int midPointX = (array[i].X + array[j].X) / 2;
int midPointY = (array[i].Y + array[j].Y) / 2;
if(mapper.containsKey(midPointX) && mapper.get(midPointX) == midPointY) {
result.add(array[i]);
result.add(array[j]);
return result;
}
}
}
return result;
}
```

//O(n^2) where n is the number of IntPoint in array and k is some constant