#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define INF 0x0ffffff
typedef unsigned int bool;
#define true 1
#define false 0
typedef enum Level{vertical, horizontal}Level;
//K=2 for this program, 2-dimensional tree

typedef struct Point{
 int x, y;
}Point;

Level numToLevel(int v){
 if(v==0)return vertical;
 else return horizontal;
}

bool pointInRectangle(Point p, Point p1, Point p2){
 if(p.x>p1.x && p.x<p2.x && p.y>p1.y && p.y<p2.y)return true;
 return false;
}

typedef struct KDTreeNode{
 Point p;
 struct KDTreeNode* leftORdown;
 struct KDTreeNode* rightORup;
 Level level; //use enum really make it more readable?
}KDTreeNode,*KDTree;

void KDTreeInsert(KDTree *root, Point p){
 if((*root)==NULL){
  (*root) = (KDTree)malloc(sizeof(KDTreeNode));
  (*root)->leftORdown=(*root)->rightORup=NULL;
  (*root)->level=vertical;
  (*root)->p=p;
 } else {
  //TODO
  KDTree tmpRoot = (*root);
  int level=0;
  KDTree child;
  if(p.x<(*root)->p.x){
   child = (*root)->leftORdown;
  }else{
   child = (*root)->rightORup;
  }
  while(child != NULL){
   tmpRoot = child;
   level = (level+1)%2;
   if((level==0 && p.x<tmpRoot->p.x) || (level==1 && p.y<tmpRoot->p.y)){
    child = tmpRoot->leftORdown;
   } else {
    child = tmpRoot->rightORup;
   }
  }
  child = (KDTree)malloc(sizeof(KDTreeNode));
  child->leftORdown = child->rightORup = NULL;
  child->p = p;
  child->level = numToLevel((level+1)%2);
  if((level==0 && p.x<tmpRoot->p.x) || (level==1 && p.y<tmpRoot->p.y)){
   tmpRoot->leftORdown = child;
  } else {
   tmpRoot->rightORup = child;
  }
 }
}

KDTree KDTreeInsert_Recursion(KDTree root, Point p, int level){
 if(root==NULL){
  root = (KDTree)malloc(sizeof(KDTreeNode));
  root->leftORdown=root->rightORup=NULL;
  root->level=numToLevel(level);
  root->p=p;
  return root;
 } else {
  if(level==0){
   if(p.x<root->p.x){
    root->leftORdown = KDTreeInsert_Recursion(root->leftORdown,p,1);
    return root;
   }else{
    root->rightORup = KDTreeInsert_Recursion(root->rightORup,p,1);
    return root;
   }
  } else {
   if(p.y<root->p.y){
    root->leftORdown = KDTreeInsert_Recursion(root->leftORdown,p,0);
    return root;
   }else{
    root->rightORup = KDTreeInsert_Recursion(root->rightORup,p,0);
    return root;
   }
  }
 }
}

void KDTreeQueryInRectangle(KDTree root, Point p1, Point p2, int level){
 if(root==NULL)return;
 if(pointInRectangle(root->p,p1,p2)){
  printf("x=%d y=%d\n",root->p.x,root->p.y);
 }
 if(level==0){
  if(p1.x<root->p.x){
   KDTreeQueryInRectangle(root->leftORdown,p1,p2,1);
  }
  if(p2.x>root->p.x){
   KDTreeQueryInRectangle(root->rightORup,p1,p2,1);
  }
 } else {
  if(p1.y<root->p.y){
   KDTreeQueryInRectangle(root->leftORdown,p1,p2,0);
  }
  if(p2.y>root->p.y){
   KDTreeQueryInRectangle(root->rightORup,p1,p2,0);
  }
 }
}

//TODO: Need some optimizing...
// because the minimal distance from a point to a point in rectangle is not all the vertical/horizontal distance
int distanceSqr(Point p1, Point p2){
 return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
int recentMin=INF;
void findNearestPoint(KDTree root, Point p, int level){
 if(root==NULL)return;
 if(distanceSqr(root->p,p)<recentMin)recentMin = distanceSqr(root->p,p);
 if(level==0){
  if(p.x<root->p.x){
   findNearestPoint(root->leftORdown,p,1);
   if(recentMin>(p.x-root->p.x)*(p.x-root->p.x)){
    findNearestPoint(root->rightORup,p,1);
   }
  } else {
   findNearestPoint(root->rightORup,p,1);
   if(recentMin>(p.x-root->p.x)*(p.x-root->p.x)){
    findNearestPoint(root->leftORdown,p,1);
   }
  }
 } else {
  if(p.y<root->p.y){
   findNearestPoint(root->leftORdown,p,0);
   if(recentMin>(p.y-root->p.y)*(p.y-root->p.y)){
    findNearestPoint(root->rightORup,p,0);
   }
  } else {
   findNearestPoint(root->rightORup,p,0);
   if(recentMin>(p.y-root->p.y)*(p.y-root->p.y)){
    findNearestPoint(root->leftORdown,p,0);
   }
  }
 }
}

int main(int argc, char const *argv[])
{
 int i;
 int dx[]={1};
 int dy[]={1};
 KDTree root = NULL;
 
 return 0;
}