/********************************************************
* Section : 10
* Roll No. : 20CS10000 / 20CS30000
* Name : Aritra Hazra
* Assignment No : LT1b
* Description : Bounding Axix-aligned Rectangle Formation
                for Positive and Negative Labelled Points
* Date : 18-May-2021
*********************************************************/

#include <stdio.h>

#define MAX 100000

int main()
{
  int pN, nN, pXMin, pYMin, pXMax, pYMax, nXMin, nYMin, nXMax, nYMax, maxX, maxY, minX, minY, i, j, k, flag = 0;
  int pX[MAX], pY[MAX], nX[MAX], nY[MAX];
  
  // take from user the positive labelled points
  printf("\n++ Enter Number of Positive-Labelled Points: ");
  scanf("%d", &pN);
  if ( pN > 0 ) {
    printf("++ Enter Positive-Labelled Points:\n");
  }
  for ( i = 0; i < pN; i++ ) {
    printf("\t-- Enter Point-%d (space-separated X,Y-values): ", i+1);
    scanf("%d %d", &pX[i], &pY[i]);
  }
  // take from user the negative labelled points
  printf("\n++ Enter Number of Negative-Labelled Points: ");
  scanf("%d", &nN);
  if ( nN > 0 ) {
    printf("++ Enter Negative-Labelled Points:\n");
  }
  for ( i = 0; i < nN; i++ ) {
    printf("\t-- Enter Point-%d (space-separated X,Y-values): ", i+1);
    scanf("%d %d", &nX[i], &nY[i]);
  }
  
  // finding maximum and minimum ranges of positive labelled points
  // to form a tight bounding rectangle with positive labelled points
  pXMin = pX[0]; pYMin = pY[0]; pXMax = pX[0]; pYMax = pY[0];
  for ( i = 1; i < pN; i++ ) {
    if ( pX[i] < pXMin ) {
      pXMin = pX[i];
    }
    if ( pY[i] < pYMin ) {
      pYMin = pY[i];
    }
    if ( pX[i] > pXMax ) {
      pXMax = pX[i];
    }
    if ( pY[i] > pYMax ) {
      pYMax = pY[i];
    }
  }
  
  // finding maximum and minimum ranges of negative labelled points
  nXMin = nX[0]; nYMin = nY[0]; nXMax = nX[0]; nYMax = nY[0];
  for ( i = 1; i < nN; i++ ) {
    if ( nX[i] < nXMin ) {
      nXMin = nX[i];
    }
    if ( nY[i] < nYMin ) {
      nYMin = nY[i];
    }
    if ( nX[i] > nXMax ) {
      nXMax = nX[i];
    }
    if ( nY[i] > nYMax ) {
      nYMax = nY[i];
    }
  }
  
  // finding the range of the canvas
  minX = (pXMin < nXMin) ? pXMin : nXMin;
  maxX = (pXMax > nXMax) ? pXMax : nXMax;
  minY = (pYMin < nYMin) ? pYMin : nYMin;
  maxY = (pYMax > nYMax) ? pYMax : nYMax;
  
  // printing the canvas
  printf("\n** Spatial Canvas with Positive and Negative Points **\n");
  for ( i = maxY; i >= minY; i-- ) {
    printf("%3d| ", i); // printing Y-axis labels
    for ( j = minX; j <= maxX; j++ ) {
      flag = 0;
      for ( k = 0; (k < pN) && !flag; k++ ) { // finding for positive points
        if ( (pX[k] == j) && (pY[k] == i) ) {
          printf("(+)");
          flag = 1;
        }
      }
      for ( k = 0; (k < nN) && !flag; k++ ) { // finding for negative points
        if ( (nX[k] == j) && (nY[k] == i) ) {
          printf("(-)");
          flag = 1;
        }
      }
      if ( !flag ) { // no points reside in [j,i] co-ordinate
        if ( (i == pYMax) || (i == pYMin) ) { // top and bottom boundary of rectangle
          if ( j == pXMin ) { // left corners
            printf(" +-");
          }
          else if ( j == pXMax ) { // right corners
            printf("-+ ");
          }
          else if ( (j > pXMin) && (j < pXMax) ) { // boundary in between left-right corners
            printf("---");
          }
          else { // outside zone of horizontal boundary
            printf("   ");
          }
        }
        else if ( (i < pYMax) && (i > pYMin) && ( (j == pXMin) || (j == pXMax) ) ) {
          // left and right boundary of rectangle
          printf(" | ");
        }
        else { // other zone points
          printf("   ");
        }
      }
    }
    printf("\n");
  }
  // printing X-axis labels
  printf("     ");
  for ( j = minX; j <= maxX; j++ ) {
    printf("-+-");
  }
  printf("\n     ");
  for ( j = minX; j <= maxX; j++ ) {
    printf("%3d",j);
  }
  
  // finding whether any negative labelled points falls inside the bounding box
  for ( i = 0, flag = 0; (i < nN) && !flag; i++ ) {
    if ( (nX[i] >= pXMin) && (nX[i] <= pXMax) && (nY[i] >= pYMin) && (nY[i] <= pYMax) ) {
      flag = 1; // indicating negative point inside rectangle
    }
  }
  
  // indicating the non-separability of positive and negative points
  if ( flag ) {
    printf("\n\n!! Note: Bounding Rectangle Contains (-) labelled Points Inside !!\n");
  }
  else {
    printf("\n\n** Axis-Aligned Bounding Rectangle Corners: (%d,%d) and (%d,%d)\n", pXMin, pYMin, pXMax, pYMax);
  }
  
  return 0;
}