일단 정신나간 소스코드 죄송합니다 ㅋㅋㅋ

우선 모든 변이 축에 평행한 정사각형들을 먼저 세두고

그 다음 하나 이상의 변이 축에 평행하지 않은 평행사변형을 찾는 코드입니다.

기준점 하나(0,0)를 잡고, 그 점으로부터 +dx, +dy 떨어진 점을 두 번째 점으로 하여 아래방향으로만 평행사변형을 만드는 코드입니다.

계산의 편의상 평행사변형이 가지는 최대 너비와 최대 높이만 구하기 위해 기준점의 좌표는 0,0을 두고 계산하였습니다.

-dx, -dy를 가지는 순감소 평생사변형의 경우는 +dx, +dy를 가지는 평행사변형을 코드상 항상 두 번 세기 때문에 따로 세지 않았습니다.

두 번째 점 (dx,dy)로부터 떨어진 거리 a와 b(절대값입니다)가 (dx,dy) 혹은 (dy,dx) 말고도 다른 방법이 있는 것을 확인하여

dx^2+dy^2=a^2+b^2인 a, b를 찾아(dx,dy 포함) 배치 가능한 모든 방법으로 배치시키고, 그 모양의 평행사변형이 그리드 내에 몇 회 출현하는지 모두 합산하는 코드를 짰습니다.

dx/dy와 a/b를 비교하여 기울기 차이에 따라 케이스를 나누어 좌표가 순증가/순감소하는 평행사변형을 셀 때를 제외하면

중복되는 경우가 없도록 셌습니다.

또한 dx^2+dy^2 자체가 제곱수일 땐 (0,0), (dx,dy)를 잇는 선분 아래에 있으면서 축과 평행하게 뻗어나간 변을 가지는 평행사변형 네 종류가 추가로 만들어지는 것까지 처리하였습니다. (실제로는 두 가지이지만 좌우 반전하여 네가지)

반례 혹은 제가 놓친 케이스가 어떤 것인지, 아니면 아이디어까진 맞았는데 구현에서 실수가 있는 건지

꼭 좀 알고 싶습니다. ㅠㅠ

메모리 100MB 사용해서 새로 짠 코드입니다.

큰 입력에서 결과가 다르게 나오는데 어찌됐든 틀렸네요

아.. ㅠㅠ.. 초라기 이후 또 이런 문제가..

자체적으로 해결했습니다. dx^2+dy^2이 제곱수일 때, 한 변이 축에 평행한 마름모를 가능한 (a,b)쌍의 갯수만큼

중복하여 세고 있는 문제가 있었습니다.

댓글을 작성하려면 로그인해야 합니다.