Computer Programming Contest Preparation

ToolBox - Source for: 102/10245/c.c



/home/toolbox/public_html/solutions/102/10245/c.c
    1 #include <stdio.h>
    2 #include <string.h>
    3 #include <sys/types.h>
    4 #include <sys/stat.h>
    5 #include <fcntl.h>
    6 #include <stdint.h>
    7 #include <math.h>
    8 #include <stdlib.h>
    9 
   10 #define TRUE  (1 == 1)
   11 #define FALSE (1 != 1)
   12 
   13 #define DEBUG if (FALSE)
   14 #define DEBUG1 if (FALSE)
   15 
   16 #define MAXPOINTS 10005
   17 #define MAXINT 0x7FFFFFFF
   18 
   19 #define MIN(a,b) (((a)<(b))?(a):(b))
   20 
   21 struct pointStruct
   22 {
   23     /* STRUCT pointStruct */
   24     double x;
   25     double y;
   26 }; /* STRUCT pointStruct */
   27 
   28 
   29 int numPoints;
   30 struct pointStruct pts[MAXPOINTS];
   31 
   32 /*
   33  *  Author: Isaac Traxler
   34  *    Date: 2014 11 6
   35  * Purpose: fun -- implement divide and conquer
   36  * Problem: 10245 - The Closest Pair
   37  */
   38 
   39 void dump()
   40 {
   41     /* FUNCTION dump */
   42     int i;
   43 
   44     printf("dump\n");
   45     printf("NumPoints=%d\n", numPoints);
   46     for (i=0; i<numPoints; i++)
   47         {
   48             /* for */
   49             printf("point %d: (%lf, %lf)\n", i, pts[i].x, pts[i].y);
   50         } /* for */
   51     printf("\n\n");
   52 } /* FUNCTION dump */
   53 
   54 int compare(const void *a, const void *b)
   55 {
   56     /* FUNCTION compare */
   57     struct pointStruct *p1 = a;
   58     struct pointStruct *p2 = b;
   59     int ret;
   60 
   61     ret = p1->x - p2->x;
   62     if (0 == ret)
   63         {
   64             /* Xs match, sort by y */
   65             ret = p1->y - p2->y;
   66         } /* Xs match, sort by y */
   67 
   68     return ret;
   69 } /* FUNCTION compare */
   70 
   71 int getInput()
   72 {
   73     /* FUNCTION getInput */
   74     int dataReadFlag;
   75     int i;
   76 
   77     dataReadFlag = FALSE;
   78     scanf("%d ", &numPoints);
   79     if (0 < numPoints)
   80         {
   81             /* then */
   82             dataReadFlag = TRUE;
   83             for (i=0; i<numPoints; i++)
   84                 {
   85                     /* for */
   86                     scanf("%lf %lf ", &pts[i].x, &pts[i].y);
   87                 } /* for */
   88             qsort(pts, numPoints, sizeof(struct pointStruct), compare);
   89         } /* then */
   90 
   91     return (dataReadFlag);
   92 } /* FUNCTION getInput */
   93 
   94 double dist(struct pointStruct p1, struct pointStruct p2)
   95 {
   96     /* FUNCTION dist */
   97     double x;
   98     double y;
   99 
  100     x = p1.x - p2.x;
  101     y = p1.y - p2.y;
  102     return (x * x + y * y);
  103 } /* FUNCTION dist */
  104 
  105 double divideAndConquer(int first, int last)
  106 {
  107     /* FUNCTION divideAndConquer */
  108     /* if 3 or fewer left -- just do it
  109        otherwise, split and do it again */
  110     double ret;
  111     double d1;
  112     double d2;
  113     double d3;
  114     int i;
  115 
  116     DEBUG printf("divideAndConquer: %d %d\n", first, last);
  117     switch (last - first)
  118         {
  119         /* deal with possible number of points */
  120         case 0:
  121             ret = -1.0;
  122             break;
  123         case 1:
  124             ret = dist(pts[first], pts[last]);
  125             DEBUG printf("case 1: %lf\n", ret);
  126             break;
  127         case 2:
  128         {
  129             /* 3 points */
  130             /*
  131             d1 = divideAndConquer(first, first + 1);
  132             d2 = divideAndConquer(first+1, last);
  133             ret = MIN(d1, d2);
  134             */
  135             ret = MIN(divideAndConquer(first, first+1), divideAndConquer(first+1, last));
  136             DEBUG printf("case 2: %lf (%lf %lf)\n", ret, d1, d2);
  137             } /* 3 points */
  138         break;
  139         default: /* lots of points */
  140         {
  141             /* lots of points left -- divide them up again */
  142             i = ( last - first) / 2;
  143             /*
  144             ret = MIN(divideAndConquer(first, first + i), divideAndConquer(first+i+1, last));
  145             */
  146 
  147             d1 = divideAndConquer(first, first + i);
  148             d2 = divideAndConquer(first+i+1, last);
  149             ret = MIN(d1, d2);
  150             DEBUG printf("case default: %lf (%lf %lf)\n", ret, d1, d2);
  151             } /* lots of points left -- divide them up again */
  152         } /* deal with possible number of points */
  153 
  154     DEBUG printf("divideAndConquer exit: %d %d\n", first, last);
  155     return ret;
  156 } /* FUNCTION divideAndConquer */
  157 
  158 double calcDelta(double x)
  159 {
  160     /* FUNCTION calcDelta */
  161     int i;
  162     int j;
  163     double delta;
  164     double delta2;
  165     double tmp;
  166 
  167     delta = sqrt(x);
  168     delta2 = x;
  169     for (i=0; (numPoints-1) > i; i++)
  170         {
  171             /* for each initial point */
  172             DEBUG printf("i=%d\n", i);
  173             for (j=i+1; (j<numPoints); j++)
  174                 {
  175                     /* check every other point to the tight within delta */
  176                     tmp = pts[j].x - pts[i].x;
  177                     DEBUG printf("j loop: %lf i %d:(%lf, %lf) - j %d:(%lf, %lf)\n", tmp, i, pts[i].x, pts[i].y, j, pts[j].x, pts[j].y);
  178                     if (tmp > delta)
  179                         {
  180                             /* bail out */
  181                             DEBUG printf("bail at %d\n", j);
  182                             j = numPoints;
  183                         } /* bail out */
  184                     else
  185                         {
  186                             /* possible points */
  187                             tmp = dist(pts[i], pts[j]);
  188                             DEBUG printf("delta(%lf^2=%lf): %lf %d:(%lf, %lf) - %d:(%lf, %lf)\n", delta, delta2, tmp, i, pts[i].x, pts[i].y, j, pts[j].x, pts[j].y);
  189                             if (tmp < delta2)
  190                                 {
  191                                     /* new low */
  192                                     delta2 = tmp;
  193                                     delta = sqrt(tmp);
  194                                     DEBUG printf("new %lf^2=%lf\n", delta, delta2);
  195                                 } /* new low */
  196                         } /* possible points */
  197                 } /* check every other point to the tight within delta */
  198         } /* for each initial point */
  199     return delta;
  200 } /* FUNCTION calcDelta */
  201 
  202 void process()
  203 {
  204     /* FUNCTION process */
  205     double d2;
  206     double delta;
  207 
  208     DEBUG1 dump();
  209 
  210     if (1 < numPoints)
  211         {
  212             /* have at least two points */
  213             d2 = divideAndConquer(0, numPoints-1);
  214             delta = calcDelta(d2);
  215 
  216             DEBUG printf("squared=%lf %lf delta: %lf\n", d2, sqrt(d2), delta);
  217 
  218             if (((double) 10000.0) > delta)
  219                 {
  220                     /* then */
  221                     printf("%.4lf\n", delta);
  222                 } /* then */
  223             else
  224                 {
  225                     /* else */
  226                     printf("INFINITY\n");
  227                 } /* else */
  228         } /* have at least two points */
  229     else
  230         printf("INFINITY\n");
  231 } /* FUNCTION process */
  232 
  233 int main ()
  234 {
  235     /* main */
  236     int moreToDo;
  237 
  238     moreToDo = getInput();
  239     while (moreToDo)
  240         {
  241             /* while */
  242             process();
  243             moreToDo = getInput();
  244         } /* while */
  245 
  246     return EXIT_SUCCESS;
  247 } /* main */
  248 
  249 
  250