Problem Scenario: Smoothie Store Finder

Given the weather and our fantastic smoothie recipes, people are constantly searching for the locations of our

stores. Therefore, you decided to develop a program to help customers find nearby smoothie stores. While

writing the code, you are assuming yourself as a customer and planning the code accordingly.

The city you are in can be modeled on the Cartesian plane. You are located at the point $($x$,$ y$).$ In addition, you

have the Cartesian coordinates of all smoothie shops around you in the city. What you would like to do is write

a program that sorts these locations based on their distance from you, followed by handling queries. The queries

are of the form of a point you are thinking of visiting. Your program should identify if there is a smoothie shop

at that location, and if so$,$ what their rank is on the sorted list of the shops. If no shop is at that location, you

should correctly identify this.

Note: There are many important implementation restrictions for this assignment, so to make sure

everyone reads these, the section on implementation restrictions will be next, changing the order of the

sections as compared to other assignments.

Implementation Restrictions

$1.$ You must use a specified combination of Merge Sort and Insertion Sort to sort the point data. Specifically,

for each input case, a threshold value, t$,$ will be given. If the subsection of the array to sort has t or fewer

values to sort, Insertion Sort should be used from the mergeSort function $($This strategy will be briefly

discussed in the class$).$ Otherwise, for larger arrays, regular merge sort should be used. The idea is that

while doing merge sort, we don$$t want to wait until the array size becomes $1.$ As soon as the array size is

smaller than the threshold, we would like to take the help of insertion sort to sort those smaller arrays.

Further details about the comparison used for the sorting are below.

$2.$ You must store your coordinates in a struct that contains two integer fields. You can add more fields if

needed.

$3.$ You must implement a ReadData$()$ function that reads the required data from the inputs and return the

array of points to be sorted.

$4.$ While comparing points during sorting, you need to use a compareTo function to decide which point should

come first out of the two points you are comparing. So$,$ you must write a function compareTo which

takes in two pointers, ptrPt$1$ and ptrPt$2,$ to coordinate structs and returns:

a$.$ a negative integer if the point pointed by ptrPt$1$ is closer to you than the point pointed to by ptrPt$2$

b$.0$ if the two locations pointed to by both are identical locations,

c$.$ a positive integer if the point pointed to by ptrPt$1$ is farther from you than the point pointed to by

ptrPt$2.$

d$.$ Exceptions to this will be when the two pointers are pointing to points that are the same distance

from you, but are distinct points.

i$.$ In these cases, if ptrPt$1\text{'}$s x coordinate is lower than ptrPt$2\text{'}$s x coordinate, a negative integer

must be returned.

ii$.$ Alternatively, if ptrPt$1\text{'}$s x coordinate is greater than ptrPt$2\text{'}$s x coordinate a positive integer

must be returned.

iii. Finally, if the x coordinate of both points is the same, if ptrPt$1\text{'}$s y coordinate is lower than

ptrPt$2\text{'}$s y coordinate, a negative integer must be returned. If ptrPt$1\text{'}$s y coordinate is greater

than ptrPt$2\text{'}$s y coordinate, a positive integer must be returned.

$5.$ Since your location must be used for sorting, please make the variable that stores your x and y coordinates

global. Your program should have no other global variables.

$6.$ A Binary Search function must be used when answering queries.

$7.$ Write a wrapper sort function that should take in the array to be sorted, the length of the array as well as

the threshold value, t$,$ previously mentioned. This function should NOT be recursive. It should be a wrapper

function. It means it will call necessary sorting function from here.

$8.$ The recursive mergesort function should take in the array, a starting index into the array, an ending index

into the array and the threshold value t$.$ In this function, either recursive calls should be made OR a call to

an insertion sort function should be made.

$9.$ Make sure to write the insertion sort function that takes the array, starting and ending index from the array

that you want to sort. Make sure you sort only from the starting and ending index of the array. Do not sort

the entire array by mistake in this function, which will increase the run$-$time a lot instead of optimizing!

The Problem

Given your location, and the location of each smoothie store, sort the list by distance from you from shortest

to longest, breaking ties by x$-$coordinate $($lower comes first$),$ and then breaking those ties by y coordinate

$($lower comes first$).$

After sorting, answer several queries about points in the coordinate plane. Specifically, determine if a query

point contains a smoothie shop or not. If so$,$ determine that