상자 4개
2010-08-06문제 출처 - http://xper.org/wiki/seminar/FourBoxes
4개의 직사각형이 평면에 있는데 밑변이 모두 가로축에 평행하다. 이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고 겹쳐 있을 수도 있다. 또한 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭지점이 겹쳐질 수도 있다. 실행 파일의 이름은 RECT.EXE로 하시오.입력형식
하나의 직사각형은 왼쪽 아래의 꼭지점과 오른쪽 위의 꼭지점의 좌표로 주어진다. 입력은 네 줄이며, 각 줄은 네 개의 정수로 하나의 직사각형을 나타낸다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭지점의 x좌표, y좌표이고, 세 번째와 네 번째의 정수는 사각형의 오른쪽 위 꼭지점의 x좌표, y좌표이다. 단, x좌표와 y좌표는 1 이상이고 1000 이하인 정수이다.
출력형식
화면에 4개의 직사각형이 차지하는 면적을 출력한다.
입력예제
1 2 4 4 2 3 5 7 3 1 6 5 7 3 8 6
출력예제
26
import java.util.ArrayList;
public class Box {
static public int[] getFourPoints(String line)
{
int points[] = {0,0,0,0};
String tempPoints[] = line.split(" ");
points[0] = Integer.parseInt(tempPoints[0]);
points[1] = Integer.parseInt(tempPoints[1]);
points[2] = Integer.parseInt(tempPoints[2]);
points[3] = Integer.parseInt(tempPoints[3]);
return points;
}
static public int[] getCrossedArea(int[][] points)
{
int[] crossedArea = {0,0,0,0};
for (int i = 0; i points[i][2])
{
int temp0 =points[i][0];
points[i][0] = points[i][2];
points[i][2] = temp0;
int temp1 =points[i][1];
points[i][1] = points[i][3];
points[i][3] = temp1;
}
}
/*겹치는 것은 다음 네가지. y축에도 같이 적용.*/
/*x1 < x3 < x2 < x4*/
if ( points[0][0] <= points[1][0] &&
points[1][0] <= points[0][2] &&
points[0][2] <= points[1][2] )
{
crossedArea[0] = points[1][0];
crossedArea[2] = points[0][2];
}
/*x3 < x1 < x4 < x2*/
else if ( points[1][0] <= points[0][0] &&
points[0][0] <= points[1][2] &&
points[1][2] <= points[0][2] )
{
crossedArea[0] = points[0][0];
crossedArea[2] = points[1][2];
}
/*x1 < x3 < x4 < x2*/
else if ( points[0][0] <= points[1][0] &&
points[1][0] <= points[1][2] &&
points[1][2] <= points[0][2] )
{
crossedArea[0] = points[1][0];
crossedArea[2] = points[1][2];
}
/*x3 < x1 < x2 < x4*/
else if ( points[1][0] <= points[0][0] &&
points[0][0] <= points[0][2] &&
points[0][2] <= points[1][2] )
{
crossedArea[0] = points[0][0];
crossedArea[2] = points[0][2];
}
/*겹치는 것은 다음 네가지. y축*/
/*y1 < y3 < y2 < y4*/
if ( points[0][1] <= points[1][1] &&
points[1][1] <= points[0][3] &&
points[0][3] <= points[1][3] )
{
crossedArea[1] = points[1][1];
crossedArea[3] = points[0][3];
}
/*y3 < y1 < y4 < y2*/
else if ( points[1][1] <= points[0][1] &&
points[0][1] <= points[1][3] &&
points[1][3] <= points[0][3] )
{
crossedArea[1] = points[0][1];
crossedArea[3] = points[1][3];
}
/*y1 < y3 < y4 < y2*/
else if ( points[0][1] <= points[1][1] &&
points[1][1] <= points[1][3] &&
points[1][3] <= points[0][3] )
{
crossedArea[1] = points[1][1];
crossedArea[3] = points[1][3];
}
/*y3 < y1 < y2 < y4*/
else if ( points[1][1] <= points[0][1] &&
points[0][1] <= points[0][3] &&
points[0][3] <= points[1][3] )
{
crossedArea[1] = points[0][1];
crossedArea[3] = points[0][3];
}
/* for(int i=0; i<4; i++) System.out.println(i+" " + crossedArea[i]);*/
return crossedArea;
}
static public int getArea(int[] points)
{
return Math.abs( (points[0] - points[2]) * (points[1] - points[3]) );
}
static public int getArea(String line)
{
return getArea(getFourPoints(line));
}
static public ArrayList convertBoxes(String boxLines)
{
ArrayList points = new ArrayList();
String[] crossedBoxes = boxLines.split("n");
int length = crossedBoxes.length;
int x = 0;
while(length > 0)
{
points.add( getFourPoints(crossedBoxes[x]) );
x++;
length--;
}
return points;
}
static public int getAllArea(String line)
{
int sumArea = 0;
ArrayList boxList = convertBoxes(line);
int[][] temp={ boxList.get(0),boxList.get(1) };
/*맨 처음 한개씩*/
/*+*/
/*A, B, C, D*/
for(int i = 0; i < 4; i++)
sumArea += getArea(boxList.get(i));
/*get*/
int tempArea= 0;
/*-*/
/*AB, AC, AD, BC, BD, CD*/
/*12, 13, 14, 23, 24, 34*/
temp[0]= boxList.get(0);
temp[1]= boxList.get(1) ;
tempArea += getArea( getCrossedArea(temp) );
temp[1]= boxList.get(2) ;
tempArea += getArea( getCrossedArea(temp) );
temp[1]= boxList.get(3) ;
tempArea += getArea( getCrossedArea(temp) );
temp[0]= boxList.get(1);
temp[1]= boxList.get(2) ;
tempArea += getArea( getCrossedArea(temp) );
temp[1]= boxList.get(3) ;
tempArea += getArea( getCrossedArea(temp) );
temp[0]= boxList.get(2);
temp[1]= boxList.get(3) ;
tempArea += getArea( getCrossedArea(temp) );
sumArea -=tempArea;
/*+*/
/*ABC, BCD, BDA, CDA*/
/*123, 124, 134 ,234*/
tempArea = 0;
/*AB*/
temp[0]= boxList.get(0);
temp[1]= boxList.get(1);
int[] tempAB= getCrossedArea(temp);
/*CD*/
temp[0]= boxList.get(2);
temp[1]= boxList.get(3);
int[] tempCD = getCrossedArea(temp);
/*ABC*/
temp[0] = tempAB;
temp[1] = boxList.get(2);
tempArea += getArea( getCrossedArea(temp) );
/*ABD*/
temp[1]= boxList.get(3) ;
tempArea += getArea( getCrossedArea(temp) );
/*ACD*/
temp[0]= tempCD;
temp[1]= boxList.get(0) ;
tempArea += getArea( getCrossedArea(temp) );
/*BCD*/
temp[1]= boxList.get(1);
tempArea += getArea( getCrossedArea(temp) );
sumArea +=tempArea;
/*-*/
/*ABCD*/
tempArea = 0;
temp[1] = tempAB;
tempArea += getArea( getCrossedArea(temp) );
sumArea -= tempArea;
return sumArea;
}
}
풀이에 걸린 시간 - 0.5 + 0.5 + 1.5 + 1 + 0.5 = 총 4 시간. 아 창피해. 그래도 좀 창피해 하고 나면 다음번엔 더 빨리 하겠지.
- 최초의 0.5 둘은 대충 기본적인 구조를 파악하고 어떻게 하면 되겠다. 라는 식의 구도를 잡는데 사용.
- 문제를 쓰고 있으려니, 언젠가 본 3각형을 겹쳐서 그 면적을 구하는 프로그램이 생각남. ...한번 본 건데도 이렇게 오래 걸렸다.
- 열심히 머리를 굴려서 n(A∪B) = n(A) + n(B) - n(A∩B)를 떠올림.
- 하지만 2개 이상은 모르겠음. ORL 기억을 뒤짐.
- 2번에서 본 프로그램에서 저런 식을 사용하되 +-를 번갈아 썼던 게 기억남. 여기까지 총 0.5시간 소요.
- 퇴근 후 독서실에서 30분간 내용을 정리하며 n(A∪B∪C∪D) = n(A) + n(B) + n(C) + n(D) - ( n(A∩B) + n(A∩C) + n(A∩D) + n(B∩C) + n(B∩D) + n(C∩D) ) + ( n(A∩B∩C) + n(A∩B∩D) + n(A∩C∩D) + n(B∩C∩D)) - n(A∩B∩C∩D) 를 도출해 냄. 잠깐 뿌듯했으나, 이미 본 거인데다가 중고교 때 수학만 좀 했었어도 하는 후회가 몰려옮. 동시에 졸려서 자러 감.
- 다음 날, 이제 다 했다는 생각으로 소스를 짜기로 결정. 언어는 요즘 제일 많이 쓰는 java로 결정.
- ...1시간 경과... ORL 을 느낌. 기본 틀에 구멍이 많았음. 손에 익었다고 생각한 java는 날 더욱 OTL...
- 기왕 java를 쓰면서 왜 배열로만 하려 했나 하는 생각을 하면서 ArrayList를 도입. 소스는 더욱 안드로메다로.
- 메소드는 간단한 것부터 완성했음. 줄 수가 그대로 순서라고 보면 됨
- 다음 날. 점심 전에 끝내자는 생각으로 다시 종이를 잡고 정리를 시작.
- 막힌 부분이었던 두 사각형이 겹치는 부분의 구현을 가로축과 세로축을 중심으로 2개 2차원으로 분할.
- 각 차원마다 기준점이 총 4개 생기므로 그 순서에 따라 겹치는 경우를 골라냄.
- 무식하게 일일이 if-else if 문을 써서 돌림
- 완성
문제점
- 일단 시간이 너무 걸렸다. 이거 보기로는 올림피아드 그런 쪽에나올 법한 문제인데, C/C++로 짠다 해도 1시간 내로 걸려야 적절할 듯.
- 코딩에 들어가는 시점이 부적절. 전체 큰 그림을 그리지도 않고, 착안만 가지고 접근했으며, 구멍이 난 걸 이해하지 못한 채로 들어갔고, 그것도 한참 짜다 알았다.
- 아직 java에 익숙하지 않다.
결론, 더 열심히 하자.