#include "treasure.h"
#include <vector>
using namespace std;
#define II pair<int,int>
struct Rect{
II topLeft; // <y, x>
II bottomRight;
int size() {
return (bottomRight.first - topLeft.first + 1) * (bottomRight.second - topLeft.second + 1);
}
};
void splitRect(Rect &in, Rect &out1, Rect &out2) {
int h = in.bottomRight.first - in.topLeft.first + 1;
int w = in.bottomRight.second - in.topLeft.second + 1;
if (w <= h) {
int midR = (in.bottomRight.first + in.topLeft.first) >> 1;
out1 = Rect{II(in.topLeft.first, in.topLeft.second), II(midR, in.bottomRight.second)};
out2 = Rect{II(midR + 1, in.topLeft.second), II(in.bottomRight.first, in.bottomRight.second)};
}else {
int midC = (in.bottomRight.second + in.topLeft.second) >> 1;
out1 = Rect{II(in.topLeft.first, in.topLeft.second), II(in.bottomRight.first, midC)};
out2 = Rect{II(in.topLeft.first, midC + 1), II(in.bottomRight.first, in.bottomRight.second)};
}
}
int savedPntLen;
II savedPnt[10004];
void reportAll(Rect &rect) {
for(int r = rect.topLeft.first; r <= rect.bottomRight.first; r++) {
for(int c = rect.topLeft.second; c <= rect.bottomRight.second; c++) {
// Report(r, c);
savedPnt[savedPntLen++] = II(r, c);
}
}
}
void printRect(Rect r) {
// printf("(%d, %d) -- (%d, %d)\n", r.topLeft.first, r.topLeft.second, r.bottomRight.first, r.bottomRight.second);
}
// return cnt
int checkRect(Rect r) {
printRect(r);
int cnt = countTreasure(r.topLeft.first, r.topLeft.second, r.bottomRight.first, r.bottomRight.second);
if (cnt == r.size()) {
// 모두 report
reportAll(r);
return cnt;
}
if (cnt == 0) return 0;
Rect r1, r2;
splitRect(r, r1, r2);
//
// printf("cnt: %d\n", cnt);
printRect(r1);
printRect(r2);
int cnt1 = checkRect(r1);
// printf("cnt1: %d\n", cnt1);
// return 0;
int cnt2 = cnt - cnt1;
// printf("cnt2: %d\n", cnt2);
if (cnt2 == r2.size()) {
reportAll(r2);
} else {
if (cnt2 == 0) {
}else{
checkRect(r2);
}
}
return cnt;
}
void callSavedReport() {
for(int i = 0; i < savedPntLen; i++) {
Report(savedPnt[i].first, savedPnt[i].second);
}
}
void findTreasure (int N) {
savedPntLen = 0;
checkRect(Rect{II(1, 1), II(N, N)});
callSavedReport();
}
