[일기] 최소, 최대 정사각형 문제였던가

104x104 배열 이용
시간복잡도 0.5*n^2 - 0.5*n

http://judge.lavida.us/problem/1001

#include <iostream>

using namespace std;

#define MAX_RANGE 104
#define NONE 0
#define EXIST 1
#define MAX_TESTCASE 20

int main(int argc, char* argv[]){

int m[MAX_RANGE*2+1][MAX_RANGE*2+1] = {0};
int testCase[MAX_TESTCASE][2] = {{0}};

int nTestCase, numOfPoints, x, y, inputCase;
int maxLength = 0, minLength = MAX_RANGE*2+1;
cin>>nTestCase;
inputCase = 0;
while(nTestCase > 0){
cin>>numOfPoints;
for(int k = numOfPoints; k > 0; k--){
cin>>x>>y;
m[y+MAX_RANGE][x+MAX_RANGE] = EXIST;
}

int tempLen = 0;
for(int i = 0; i<MAX_RANGE*2+1; i++){
for(int j = 0; j<MAX_RANGE*2+1; j++){
if(m[i][j] == EXIST){
x = j;
y = i;
for(int k = x+1; k < MAX_RANGE*2+1; k++){
if(m[y][k] == EXIST){
tempLen = (k-x);
if(y+tempLen >= MAX_RANGE*2+1) {
break;
}
bool flag = (m[y+tempLen][k] == EXIST)?(true):(false);
bool flag2 = (m[y+tempLen][x] == EXIST)?(true):(false);

if(flag && flag2){
if(tempLen - minLength < 0)
minLength = tempLen;
if(tempLen - maxLength > 0)
maxLength = tempLen;
}
}
}
}
}
}

testCase[inputCase][0] = minLength;
testCase[inputCase][1] = maxLength;
minLength = MAX_RANGE*2+1;
maxLength = 0;
nTestCase--;
inputCase++;

for(int i = 0; i<MAX_RANGE*2+1; i++)
for(int j = 0; j <MAX_RANGE*2+1; j++)
m[i][j] = NONE;

}

for(int i = 0; i < inputCase; i++){
cout<<testCase[i][0]<<" "<<testCase[i][1]<<endl;
}

return 0;
}