slatenails

find_rings_2.cc

Oct 16th, 2013
63
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <deque>
  4. #include <cmath>
  5.  
  6. struct Component
  7. {   int num;
  8.     double scale;
  9. };
  10.  
  11. std::deque<Component> solution;
  12.  
  13. template<class T> inline T abs (T a)
  14. {   return (a > 0) ? a : -a;
  15. }
  16.  
  17. inline bool isZero (double a)
  18. {   return abs<double> (a) < 0.0001;
  19. }
  20.  
  21. inline bool isInteger (double a)
  22. {   return isZero (a - (int) a);
  23. }
  24.  
  25. // =============================================================================
  26. // ringFinder
  27. //
  28. // This is the main algorithm of the ring finder. It tries to use math to find
  29. // the one ring between r0 and r1. If it fails (the ring number is non-integral),
  30. // it finds an intermediate radius (ceil of the ring number times scale) and
  31. // splits the radius at this point, calling this function again to try find the
  32. // rings between r0 - r and r - r1.
  33. //
  34. // This does not always yield into usable results. If at some point r == r0 or
  35. // r == r1, there is no hope of finding the rings, at least with this algorithm,
  36. // as it would fall into an infinite recursion.
  37. // -----------------------------------------------------------------------------
  38. bool ringFinder (double r0, double r1)
  39. {   // Find the scale and number of a ring between r1 and r0.
  40.     double scale = r1 - r0;
  41.     double num = r0 / scale;
  42.  
  43.     // If the ring number is integral, we have found a fitting ring to r0 -> r1!
  44.     if (isInteger (num))
  45.     {   Component cmp;
  46.         cmp.scale = scale;
  47.         cmp.num = (int) ceil (num);
  48.         solution.push_back (cmp);
  49.     }
  50.     else
  51.     {   // If not, find an intermediate <r> between the radii
  52.         double r = ceil (num) * scale;
  53.  
  54.         // If r is the same as r0 or r1, we simply cannot find any rings between
  55.         // r0 and r1. Stop and return failure.
  56.         if (isZero (r0 - r) || isZero (r1 - r))
  57.             return false;
  58.  
  59.         // Split this ring into r0 -> r and r -> r1. Recurse to possibly find
  60.         // the rings for these. If either recurse fails, the entire algorithm
  61.         // fails as well.
  62.         if (!ringFinder (r0, r) || !ringFinder (r, r1))
  63.             return false;
  64.     }
  65.  
  66.     // The algorithm did not fail, thus we succeeded!
  67.     return true;
  68. }
  69.  
  70. int main (int argc, char* argv[])
  71. {   char* endptr0, *endptr1;
  72.     double r0, r1;
  73.  
  74.     if (argc != 3)
  75.     {   fprintf (stderr, "usage: %s <r0> <r1>\n", argv[0]);
  76.         return 1;
  77.     }
  78.  
  79.     r0 = strtod (argv[1], &endptr0);
  80.     r1 = strtod (argv[2], &endptr1);
  81.  
  82.     if (*endptr0 != '\0' || *endptr1 != '\0')
  83.     {   fprintf (stderr, "error: arguments are not numbers\n");
  84.         return 1;
  85.     }
  86.  
  87.     if (r0 > r1)
  88.         std::swap (r0, r1);
  89.  
  90.     if (!ringFinder (r0, r1))
  91.     {   printf ("Failed to find rings for %g - %g\n", r0, r1);
  92.         exit (EXIT_FAILURE);
  93.     }
  94.  
  95.     for (std::deque<Component>::iterator it = solution.begin(); it != solution.end(); ++it)
  96.         printf ("Ring %d, scale by %g (%g -> %g)\n", it->num, it->scale,
  97.             it->num * it->scale, (it->num + 1) * it->scale);
  98. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×