You can use Quickselect:
- Select a pivot (randomly would be a good idea)
- Partition the array around that pivot according to their x coordinates, keeping track of the sum s of items you put to the left side of it
- If s ≥ 1/2, recurse into the left side. Else, recurse into the right side
The problem here is the run time is O(n²) in the worst case. However, it is O(n) on average (assuming the elements are somewhat evenly distributed). There are other partition-based selection algorithms with deterministic linear time which you can probably adapt in a similar way, but they are more complicated.