overlap point

이번에도 역시 codefight

https://codefights.com/challenge/7BLpypv6zjpr25iPY/solutions

1등은 이번에도 역시 같은 사람

코드는
#define f(x) hypot(i/9-4-x 0], i%9-4-x 1])<=x 2]
int i, r;
template <class T>
int overlapPoint(T a, T b) {
  for(;i++<99;)
      r+=f(a[) & f(b[);
  return r;
}

볼때마다 배울 것이 생기니까 아직까지는 지루하지 않다. 볼 시간이 많지 않은것이 흠이라면 흠.

핵심은 두가지다. 하나는 hypot함수, 하나는 평면의 격자를 루프 한번에 해결하는 것.
hypot함수 외에도 math.h에 희한한 함수들이 더 있는 것 같은데 처음 봤다. 짬날때 봐야 할 것 같다(하지만 보지 않겠지 -_-)

평면의 모든 격자는 예를 들어 다음과 같이 하면 쉽다
for(; x--; )
  for(; y--; )
    // do sth. (x,y) coord.

위에서는 변수를 하나만 만들고 정수 나눗셈과 modular를 이용해서 모든 격자점을 구해낸다. 참 놀라운 아이디어다.
99까지밖에 루프를 돌지 않는데 이건 테스트케이스가 작아서 운이 좋았던 것 같다. 그래도 예상할 수 있는 모든 범위에 대해 확장할 수 있으니 큰 문제는 없어보인다.

아래는 mathematica로 격자점을 구해본것. 격자점이 어떻게 모두 구해지는지 조금 더 직관적으로 볼 수 있다.

In[148]:= i = Range[0, 99]

Out[148]= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, \
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, \
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, \
51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, \
68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, \
85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99}

In[157]:= i / 9 - 4 // Floor

Out[157]= {-4, -4, -4, -4, -4, -4, -4, -4, -4, -3, -3, -3, -3, -3, \
-3, -3, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, \
-1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, \
1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, \
4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, \
6, 7}

In[158]:= Mod[i, 9] - 4

Out[158]= {-4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, \
4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, \
-3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, \
-1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, \
1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, 3, 4, -4, -3, -2, -1, 0, 1, 2, \
3, 4, -4}

In[160]:= {%157, %158} // Transpose

Out[160]= {{-4, -4}, {-4, -3}, {-4, -2}, {-4, -1}, {-4, 0}, {-4, 
  1}, {-4, 2}, {-4, 3}, {-4, 
  4}, {-3, -4}, {-3, -3}, {-3, -2}, {-3, -1}, {-3, 0}, {-3, 1}, {-3, 
  2}, {-3, 3}, {-3, 4}, {-2, -4}, {-2, -3}, {-2, -2}, {-2, -1}, {-2, 
  0}, {-2, 1}, {-2, 2}, {-2, 3}, {-2, 
  4}, {-1, -4}, {-1, -3}, {-1, -2}, {-1, -1}, {-1, 0}, {-1, 1}, {-1, 
  2}, {-1, 3}, {-1, 4}, {0, -4}, {0, -3}, {0, -2}, {0, -1}, {0, 
  0}, {0, 1}, {0, 2}, {0, 3}, {0, 
  4}, {1, -4}, {1, -3}, {1, -2}, {1, -1}, {1, 0}, {1, 1}, {1, 2}, {1, 
  3}, {1, 4}, {2, -4}, {2, -3}, {2, -2}, {2, -1}, {2, 0}, {2, 1}, {2, 
  2}, {2, 3}, {2, 4}, {3, -4}, {3, -3}, {3, -2}, {3, -1}, {3, 0}, {3, 
  1}, {3, 2}, {3, 3}, {3, 4}, {4, -4}, {4, -3}, {4, -2}, {4, -1}, {4, 
  0}, {4, 1}, {4, 2}, {4, 3}, {4, 
  4}, {5, -4}, {5, -3}, {5, -2}, {5, -1}, {5, 0}, {5, 1}, {5, 2}, {5, 
  3}, {5, 4}, {6, -4}, {6, -3}, {6, -2}, {6, -1}, {6, 0}, {6, 1}, {6, 
  2}, {6, 3}, {6, 4}, {7, -4}}