My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
 
       
// D24 => 2^24

       
unsigned int size = 1 << 24;
       
 
       
// return true if pixel at (x,y) is black

       
bool isBlack(unsigned int x, unsigned int y)
       
{
       
  // 2^(N-1)
       
  long long middle = size >> 1;
       
  // right side of the equation: 2^(2N - 2) = 2^(N-1) * 2^(N-1) = middle * middle
       
  auto threshold = middle * middle;
       
 
       
  // be a bit careful with negative differences
       
  auto dx = (long long)x - middle;
       
  auto dy = (long long)y - middle;
       
  return dx*dx + dy*dy <= threshold;
       
}
       
 
       
// return size of optimal encoding
       
// note: I expect only valid input, such that (toX - fromX) = (toY - fromY) = a power of two

       
unsigned int encode(unsigned int fromX, unsigned int fromY, unsigned int toX, unsigned int toY, bool isFirst = true)
       
{
       
  // a single pixel ?
       
  if (fromX == toX) // implies fromY == toY
       
    return 2; // doesn't matter whether black or white, both encodings need two bits
       
 
       
  // isBlack() will produce a black circle
       
  // checking all four corners is sufficient to know when to split
       
  bool a = isBlack(fromX, fromY);
       
  bool b = isBlack(toX,   fromY);
       
  bool c = isBlack(toX,   toY);
       
  bool d = isBlack(fromX, toY);
       
 
       
  // same color on all four corner => the whole area is covered by the same color
       
  // however, this assumption doesn't hold on the first level
       
  if (a == b && b == c && c == d && !isFirst)
       
    return 2; // again: the color doesn't matter, both need two bits to fill the entire area
       
 
       
  // speed optimization: if a 2x2 area needs to be split, then it always requires 9 bits
       
  if (fromX + 1 == toX)
       
    return 1 + 4*2; // a split marker and four single pixels (2 bits each)
       
 
       
  // split evenly
       
  auto half = (toX - fromX + 1) / 2;
       
  return encode(fromX,        fromY + half, toX - half, toY,        false) + // upper-left
       
         encode(fromX + half, fromY + half, toX,        toY,        false) + // upper-right
       
         encode(fromX,        fromY,        toX - half, toY - half, false) + // lower-left
       
         encode(fromX + half, fromY,        toX,        toY - half, false) + // lower-right
       
         1; // don't forget: there's one bit for the split marker
       
}
       
 
       
int main()
       
{
       
  // D24 => 24
       
  unsigned int shift = 4;
       
  std::cin >> shift;
       
 
       
  // length of an edge of the image in pixels
       
  size = 1 << shift;
       
 
       
  // draw on screen (only useful for very small values of "shift" 1 ... 5)
       
#define DRAW_IMAGE
       
#ifdef DRAW_IMAGE
       
  if (size <= 5)
       
  {
       
    for (unsigned int y = 0; y < size; y++)
       
    {
       
      auto flipY = (size - 1) - y; // problem states that lower-left corner is (0,0), must flip image upside-down
       
      for (unsigned int x = 0; x < size; x++)
       
        std::cout << (isBlack(x, flipY) ? "B" : ".");
       
      std::cout << std::endl;
       
    }
       
  }
       
#endif
       
 
       
  // let's compress to infinity and beyond !
       
  std::cout << encode(0, 0, size - 1, size - 1) << std::endl;
       
  return 0;
       
}

This solution contains 12 empty lines, 18 comments and 4 preprocessor commands.