#include "treasure.h"
#include<cstdio>
#include<vector>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
/*
ab
cd
ab, bd, dc,ac로 접근
*/
void findTreasure(int r1, int c1, int r2, int c2, int remain,vii& v)
{
/*
int k;
scanf("%d",&k);
printf("{{%d,%d},{%d,%d},%d}\n",r1,c1,r2,c2,remain);
*/
if(r1>r2||c1>c2)
return ;
if(remain ==(r2-r1+1)*(c2-c1+1))//사각형안에 1꽉차있으면
{
for(int i=r1;i<=r2;i++)
for(int j=c1;j<=c2;j++)
v.push_back(make_pair(i,j));
}
else if(remain>0)//사각형안에 1이 있긴하면
{
if(r1==r2)//무한루프때문에
{
int cmid = (c1+c2)/2;
int a = countTreasure(r1,c1,r1,cmid);
if(a==remain)
findTreasure(r1,c1,r1,cmid,remain,v);
else if(a==0)
findTreasure(r1,cmid+1,r1,c2,remain,v);
else
{
findTreasure(r1,c1,r1,cmid,a,v);
findTreasure(r1,cmid+1,r1,c2,remain-a,v);
}
}
else if(c1==c2)
{
int rmid = (r1+r2)/2;
int a = countTreasure(r1,c1,rmid,c1);
if(a==remain)
findTreasure(r1,c1,rmid,c1,remain,v);
else if(a==0)
findTreasure(rmid+1,c1,r2,c1,remain,v);
else
{
findTreasure(r1,c1,rmid,c1,a,v);
findTreasure(rmid+1,c1,r2,c1,remain-a,v);
}
}
else
{
int rmid = (r1+r2)/2;
int cmid = (c1+c2)/2;
int ab;
ab = countTreasure(r1,c1,rmid,c2);
if(ab == remain)
findTreasure(r1,c1,rmid,c2,remain,v);
else if(ab==0)//cd == remain
findTreasure(rmid+1,c1,r2,c2,remain,v);
else
{
int ac = countTreasure(r1,c1,r2,cmid);
if(ac == remain)
findTreasure(r1,c1,r2,cmid,remain,v);
else if(ac==0)//bd == remain
findTreasure(r1,cmid+1,r2,c2,remain,v);
else//d를알아야함
{
/*
int d = countTreasure(rmid+1,cmid+1,r2,c2);<<홀수일떄 더작기때문에 바꿈
int c = remain-ab-d;
int b = remain-ac-d;
int a = ac-c;
*/
int a = countTreasure(r1,c1,rmid,cmid);
int b = ab-a;
int c = ac-a;
int d = remain-a-b-c;
findTreasure(r1,c1,rmid,cmid,a,v);
findTreasure(r1,cmid+1,rmid,c2,b,v);
findTreasure(rmid+1,c1,r2,cmid,c,v);
findTreasure(rmid+1,cmid+1,r2,c2,d,v);
}
}
}
}
}
void findTreasure (int N) {
vii v;
int cnt = countTreasure(1,1,N,N);
if(cnt)
findTreasure(1,1,N,N,cnt,v);
for(vii::iterator iter = v.begin(); iter!=v.end(); iter++)
Report(iter->first,iter->second);
}
