home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / Secret Folder / Problem 03 / Secret.cp < prev    next >
Encoding:
Text File  |  1998-06-11  |  4.6 KB  |  171 lines  |  [TEXT/CWIE]
  1. #include "Solution.h"
  2.  
  3. #include "ProblemUtils.h"
  4.  
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <Files.h>
  8. #include <Errors.h>
  9.  
  10. const int MAX_HOMES = 10000;
  11.  
  12. static OSErr Read2UInt32FromHandle( Handle data, UInt32 *number1, UInt32 *number2 )
  13. {
  14.     OSErr err;
  15.     char line[MAX_LINE_LEN];
  16.     char *p;
  17.  
  18.     p = line;    
  19.     if ( ProblemReadLineFromHandle( data, line, MAX_LINE_LEN )
  20.                 && ProblemGetUInt32( &p, number1 )
  21.                 && ProblemGetUInt32( &p, number2 ) && *p == 0 ) {
  22.         err = noErr;
  23.     } else {
  24.         err = -1;
  25.     }
  26.     return err;
  27. }
  28.  
  29. static OSErr Read2SInt32FromHandle( Handle data, SInt32 *number1, SInt32 *number2 )
  30. {
  31.     OSErr err;
  32.     char line[MAX_LINE_LEN];
  33.     char *p;
  34.  
  35.     p = line;    
  36.     if ( ProblemReadLineFromHandle( data, line, MAX_LINE_LEN )
  37.                 && ProblemGetSInt32( &p, number1 )
  38.                 && ProblemGetSInt32( &p, number2 ) && *p == 0 ) {
  39.         err = noErr;
  40.     } else {
  41.         err = -1;
  42.     }
  43.     return err;
  44. }
  45.  
  46. static int Quadrant( Node *pt, SInt32 x, SInt32 y )
  47. {
  48.     if ( pt->xCoord > x ) {
  49.         if ( pt->yCoord > y ) {
  50.             return 0;
  51.         } else {
  52.             return 3;
  53.         }
  54.     } else {
  55.         if ( pt->yCoord > y ) {
  56.             return 1;
  57.         } else {
  58.             return 2;
  59.         }
  60.     }
  61. }
  62.  
  63. #define VERTEX(i) homesToEnclose[nodesInPerimeter[i]]
  64.  
  65. static Boolean Inside( Node homesToEnclose[], UInt32 numNodesInPerimeter, UInt32 nodesInPerimeter[], UInt32 home )
  66. {
  67.     SInt32 i, angle, quad, next_quad, delta;
  68.     Node last_vertex, next_vertex;
  69.     Node pt = homesToEnclose[home];
  70.     
  71.     angle = 0;
  72.     last_vertex = VERTEX(numNodesInPerimeter-1);
  73.     quad = Quadrant( &last_vertex, pt.xCoord, pt.yCoord );
  74.     for ( i = 0; i < numNodesInPerimeter; i++ ) {
  75.         next_vertex = VERTEX(i);
  76.         next_quad = Quadrant( &next_vertex, pt.xCoord, pt.yCoord );
  77.         delta = next_quad - quad;
  78.         switch ( delta ) {
  79.             case 3:
  80.                 delta = -1;
  81.                 break;
  82.             case -3:
  83.                 delta = 1;
  84.                 break;
  85.             case 2:
  86.             case -2:
  87.                 if ( (next_vertex.xCoord - pt.xCoord) * (last_vertex.yCoord - next_vertex.yCoord) > (next_vertex.yCoord - pt.yCoord) * (last_vertex.xCoord - next_vertex.xCoord) ) {
  88.                     delta = -delta;
  89.                 }
  90.                 break;
  91.         }
  92.         angle = angle + delta;
  93.         quad = next_quad;
  94.         last_vertex = next_vertex;
  95.     }
  96.     return (angle == 4) || (angle == 0) || (angle == -4);
  97. }
  98.  
  99. static Node homesToEnclose[MAX_HOMES];
  100. static Node saved_homesToEnclose[MAX_HOMES];
  101. static UInt32 nodesInPerimeter[MAX_HOMES];
  102.  
  103. pascal OSErr CheckPerimiter( const FSSpec* infile, const FSSpec* outfile, Boolean *correct )
  104. {
  105.     OSErr err;
  106.     Handle indata;
  107.     UInt32 perimiter_squared, returned_perimiter_squared;
  108.     UInt32 i, j;
  109.     UInt32 numHomes;
  110.     UInt32 numNodesInPerimeter;
  111.     
  112.     *correct = false;
  113.     
  114.     err = ProblemFileRead( infile, &indata );
  115.     ProblemLogError( err, "CheckPerimiter: ProblemFileRead" );
  116.     if ( err == noErr ) {
  117.         err = Read2UInt32FromHandle( indata, &numHomes, &perimiter_squared );
  118.         if ( err == noErr ) {
  119.             for ( UInt32 i = 0; i < numHomes && err == noErr; i++ ) {
  120.                 err = Read2SInt32FromHandle( indata, &homesToEnclose[i].xCoord, &homesToEnclose[i].yCoord );
  121.                 saved_homesToEnclose[i] = homesToEnclose[i];
  122.             }
  123.         }
  124.         ProblemLogError( err, "CheckPerimiter: Problem Reading" );
  125.         if ( err == noErr ) {
  126.             Perimeter( numHomes, homesToEnclose, &numNodesInPerimeter, nodesInPerimeter );
  127.             *correct = 0 <= numNodesInPerimeter && numNodesInPerimeter <= numHomes;
  128.  
  129.             // Check based inputs
  130.             for ( i = 0; i < numHomes && *correct; i++ ) {
  131.                 *correct = homesToEnclose[i].xCoord == saved_homesToEnclose[i].xCoord
  132.                                 && homesToEnclose[i].yCoord == saved_homesToEnclose[i].yCoord;
  133.             }
  134.             
  135.             // Check for duplicate or illegal nodes in fence
  136.             for ( i = 0; i < numNodesInPerimeter && *correct; i++ ) {
  137.                 *correct = 0 <= nodesInPerimeter[i] && nodesInPerimeter[i] < numHomes;
  138.                 for ( j = 0; j < numNodesInPerimeter && *correct; j++ ) {
  139.                     if ( i != j && nodesInPerimeter[i] == nodesInPerimeter[j] ) {
  140.                         *correct = false;
  141.                     }
  142.                 }
  143.             }
  144.             
  145.             if ( *correct ) {
  146.                 returned_perimiter_squared = 0;
  147.                 if ( numNodesInPerimeter >= 2 ) {
  148.                     for ( i = 0; i < numNodesInPerimeter && *correct; i++ ) {
  149.                         UInt32 n1 = nodesInPerimeter[i];
  150.                         UInt32 n2 = nodesInPerimeter[(i+1) % numNodesInPerimeter];
  151.                         returned_perimiter_squared += (homesToEnclose[n1].xCoord - homesToEnclose[n2].xCoord)
  152.                                                                         * (homesToEnclose[n1].xCoord - homesToEnclose[n2].xCoord);
  153.                         returned_perimiter_squared += (homesToEnclose[n1].yCoord - homesToEnclose[n2].yCoord)
  154.                                                                         * (homesToEnclose[n1].yCoord - homesToEnclose[n2].yCoord);
  155.                     }
  156.                 }
  157.                 *correct = returned_perimiter_squared == perimiter_squared;
  158.             }
  159.             
  160.             if ( *correct ) {
  161.                 for ( i = 0; i < numHomes && *correct; i++ ) {
  162.                     *correct = Inside( homesToEnclose, numNodesInPerimeter, nodesInPerimeter, i );
  163.                 }
  164.             }
  165.             
  166.         }
  167.         DisposeHandle( indata );
  168.     }
  169.     return err;
  170. }
  171.