// Tanvir Ahmed
// Solution to COP 3502 Program #3 (Dr. Ahmed's version)
// 7/5/2020

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct point
{
  int x;
  int y;
  int dist;
} point;

int refX, refY;


int binarySearch(point arr[], point query, int n);
void insertionSort(point arr[], int l, int r) ;
void merge(point arr[], int l, int m, int r);
void mergeSort(point arr[], int l, int r, int T);
void sort(point arr[], int length, int threshold);
int compareTo(point *ptrPt1, point *ptrPt2);
point* ReadData(FILE* fp, int N, int cx, int cy);
void printResults(point* inputArray, int numPoints);
//void loadPoint(point *p, int x, int y);


int main()
{
  //int radius;
  int N; //number of points
  int S; //number of points to search
  int T; //threshold while sorting

  //opening the file for reading and writing
  FILE *out = fopen("out.txt", "w");
  FILE *input = fopen("in3.txt","r");

  if(input != NULL)
  {

   //for an array of points
    point *points;

    // First 5 in in the first line of the file. Global refX and refY being read too
    fscanf(input, "%d", &refX);
    fscanf(input, "%d", &refY);

    fscanf(input, "%d", &N);
    fscanf(input, "%d", &S);
    fscanf(input, "%d", &T);

    points = ReadData(input, N, refX, refY);

    //sorting the data
    sort(points, N, T);

    //insertionSort(points, 0, N-1); //debug line to check insertion sort

    //writing the sorted data to a txt file
    for(int i = 0; i < N; i++)
    {
       //fprintf(out, "%d %d %d\n", points[i].dist, points[i].x, points[i].y);
       fprintf(out, "%d %d\n", points[i].x, points[i].y);
    }

    printf("Sorted and output written\n\n");

    //searching phase. Search the S number of points from the file
    int c = 0;
    while(c<S)
    {
        //taking input from the user
        int x,y;
        fscanf(input, "%d %d", &x, &y);

        point query;
        query.x = x;
        query.y = y;

        //searching for the point
        int r = binarySearch(points, query, N-1);
        if(r>=0)
         fprintf(out, "%d %d found at rank %d\n", x, y, r+1);
        else
          fprintf(out, "%d %d not found\n", x, y);

        c++;
    }

    fclose(input);
    fclose(out);

    free(points);

    }
    return 0;
}

int calculate_distance(point p1, point p2)
{
  //not doing square root to prevent fractional number
  return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}


//if found, returns the location, returns -1 if not found
int binarySearch(point arr[], point query, int n)
{

    point refPoint;
    refPoint.x = refX;
    refPoint.y = refY;
    //find the query point distance based on reference point and query point
    query.dist = calculate_distance(query, refPoint) ;
    //printf("distance %d ", query.dist);
    int l = 0;
    int h = n;
    while(l <= h)
    {
        //getting the middle value
        int m = (l + h)/2;
        //debug
        /*if(query.x == 0 && query.y == -5)
        {
         // printf("mid  = %d, arr[m] = %d, %d  and cmp = %d\n", m, arr[m].x, arr[m].y, compareTo(&arr[m], &query));

        }*/

        if(compareTo(&arr[m], &query) == 0)
          return m;

        if(compareTo(&arr[m], &query) <0)
          l = m + 1;
        else if(compareTo(&arr[m], &query) >0)
          h = m - 1;
    }
    return -1;

}


void merge(point arr[], int l, int m, int r)
{
    //sizes of the temporary arrays
    int size1 = (m-l) + 1;
    int size2 = (r-m);

  //create the left and right array
    point *arr1 = (point*)malloc(size1*sizeof(point));
    point *arr2 = (point*)malloc(size2*sizeof(point));

    //creating arrays 1 and 2
    for(int i = 0; i < size1; i++)
        arr1[i] = arr[i + l];


    for(int i = 0; i < size2; i++)
        arr2[i] = arr[i + m + 1];

    int p1, p2, p3; //pointers to the arrays.
    p1 = 0;
    p2 = 0;
    p3 = l;

    //checking for the smallest elements and inserting them to final array
    while(p1 < size1 && p2 < size2)
    {
        if(compareTo(&arr1[p1], &arr2[p2]) < 0)
        {
          arr[p3] = arr1[p1];
          p1++;

        }
        else
        {
            arr[p3] = arr2[p2];
            p2++;
        }
        p3++;
    }

    //copying the remaining  points in the left array (if any).
    while(p1 < size1)
    {
        arr[p3] = arr1[p1];
        p1++;
        p3++;
    }

//copying the remaining  points in the fight array (if any).
    while(p2 < size2)
    {
        arr[p3] = arr2[p2];
        p2++;
        p3++;
    }

    free(arr1);
    free(arr2);

}

void mergeSort(point arr[], int l, int r, int T)
{
    if( (r - l) <= T)
      insertionSort(arr, l, r);
    else
    if(l<r)
    {
        int mid = (l+r)/2;
        mergeSort(arr,l,mid, T);
        mergeSort(arr,mid+1,r, T);
        merge(arr,l,mid,r);
    }
}

void sort(point arr[], int length, int threshold) {
    mergeSort(arr, 0, length-1, threshold);
}

/* Reading data from file and loading it in pont array */
point* ReadData(FILE *input, int N, int cx, int cy){
    point refPoint = {cx, cy};
    // creation and population of the array of ordered pairs taken from the input file
    point* inputArray = malloc(sizeof(point) * N);
    int i = 0;

    while(i<N){
        fscanf(input, "%d", &inputArray[i].x);
        fscanf(input, "%d", &inputArray[i].y);
        inputArray[i].dist  =calculate_distance(inputArray[i], refPoint);
       // inputArray[i].dist = round(sqrt(pow((inputArray[i].x-cx), 2) + pow((inputArray[i].y-cy), 2)));
        i++;
    }

    return inputArray;

}

/* Function to sort an array using insertion sort*/
void insertionSort(point arr[], int l, int r)
{
	int i, j;
  int n = r-l+1;
  point item;
	for (i = l+1; i <=r; i++) {
		item = arr[i];
      for(j=i-1; j>=l; j--)
      {
        if(compareTo(&arr[j], &item)>0)
            arr[j+1] = arr[j]; //shift the item
        else
          break;
      }
      arr[j+1] = item;
    }
}

// A utility function to print an array of size n . Might be useful for debugging
void printArray(point arr[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d %d\n", arr[i].x, arr[i].y);
	printf("\n");
}


/* takes two pionts and compare them basedon distance first, then x (if same distance), and then y (if same distance and same x)
Based on the above comparison, the funciton returns a negative int if first point is smaller than second point
returns a positive int  if first pint is greater
returns zero if point points are same
*/
int compareTo(point *ptrPt1, point *ptrPt2)
{
  //firt compare distance
  if (ptrPt1->dist != ptrPt2->dist)
    return ptrPt1->dist - ptrPt2->dist;

  //if same distance, then compare x
  if (ptrPt1->x != ptrPt2->x)
    return ptrPt1->x - ptrPt2->x;

  //if same distance, same x, then compare y
  if (ptrPt1->y != ptrPt2->y)
    return ptrPt1->y - ptrPt2->y;

  return 0;

}