홈 › 카테고리 › 프로그래밍 문제

Four Box

토, 2007-02-17 17:16 — 귤

문제

Quote:
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


‹ 다이아몬드 그리기 졸리 점퍼(jolly jumper) ›

댓글 보기 옵션

원하시는 댓글 전시 방법을 선택한 다음 "설정 저장"을 누르셔서 적용하십시오.
토, 2007-02-17 17:16 — 귤

하스켈 버전

어떤 크기의 직사각형이든지 가로, 세로의 길이가 1인 정사각형들로 이뤄져있다고 생각할 수 있다. 벽면에 타일을 붙이듯이 말이다. 그러면 이 ‘타일’ 개수만 세면 직사각형의 넓이를 바로 구할 수 있다. 

module Main where 

import Data.Set(union, fromList) 

rect (x1:y1:x2:y2:[]) = fromList [(x,y)| x <- [x1..x2-1], y <- [y1..y2-1]]
getRectList input = map (rect . (map read) . words) input
grossArea list = foldl1 union list 

main = do
        input <- sequence $ take 4 $ repeat getLine
        print $ length $ grossArea $ getRectList input

위 프로그램에서는 ‘타일’의 좌표를 왼쪽 아래 모서리를 기준으로 한다. rect 함수는 직사각형의 두 모서리 좌표를 받아서 그 안에 들어있는 ‘타일’의 리스트를 돌려준다.
List 모듈의 union 함수는 두 리스트의 합집합을 만든다. 예를 들어 union [1,2,3] [3,4,5]라면 [1,2,3,4,5]를 내놓는다. grossArea 함수는 직사각형들이 가지고 있는 ‘타일’ 목록을 왼쪽에서부터 union 함수를 이용해 합친다음 length로 ‘타일’의 개수를 센다. ‘타일’의 넓이가 1이므로 ‘타일’의 개수는 곧 전체 사각형들의 넓이와 같다.
이 알고리즘은 구현하기가 무척 쉽다. 프로그램을 만드는 데 9분 밖에 걸리지 않았다. 그러나 사각형의 크기가 커질 수록 속도가 기하급수적으로 느려지고, 메모리를 엄청나게 소모한다.

일, 2007-03-18 19:40 — soulmate

조금 다르게 푼 방법

수학에서 배우듯이 네 집합의 합집합은

n(AUBUCUD) = n(A)+n(B)+n(C)+n(D) - {n(A∩B)+n(A∩C)+...+n(C∩D)}
+ {n(A∩B∩C)...+n(B∩C∩D)} - n(A∩B∩C∩D)

입니다.

그래서 각 사각형을 A, B, C, D라 하고,
A의 넓이, B의 넓이, C의 넓이, D의 넓이, A∩B의 넓이.. 등을 구하여
이들을 각각 위 식에 넣고 더해서 빼어서 코드를 만들었습니다.

	{- 점과 사각형의 자료형을 정의 -}
	data Points = Point Integer Integer
	data Rects = Rect Points Points
	
	{- 두 수 중 작은 수와 큰 수를 얻는 함수 -}
	min2 a b = if (a<b) then a else b
	max2 a b = if (a<b) then b else a
	
	{- 두 사각형이 겹침으로써 만들어지는 두 사각형의 왼쪽 위 점과 오른쪽 아래 점을 구하는 함수 -}
	getlimt_ul a b c d e f g h =
		Point (max2 a e) (max2 b f)
	getlimit_dr a b c d e f g h =
		Point (min2 c g) (min2 d h)
	
	{- 만들어진 사각형이 유효하도록, 즉 왼쪽 위 점이 오른쪽 아래 점보다 더 왼쪽 위에 있도록 하는 함수 -}
	makevalid (Rect (Point a b) (Point c d)) =
		if ( a<=c && b<=d 	) then
			(Rect (Point a b) (Point c d))
		else
			(Rect (Point 1 1) (Point 1 1))
	
	{- 두 사각형이 겹침으로써 만들어지는 사각형을 구하는 함수 -}
	getcap (Rect (Point a b) (Point c d)) (Rect (Point e f) (Point g h)) =
		makevalid (Rect (getlimt_ul a b c d e f g h) (getlimit_dr a b c d e f g h))
		
	{- 사각형의 넓이를 구하는 함수 -}
	getarea (Rect (Point a b) (Point c d)) =
		(c-a)*(d-b)
	
	{- 입력 인수 -}
	arg = [Rect (Point 1 2) (Point 4 4),
			  Rect (Point 2 3) (Point 5 7),
			  Rect (Point 3 1) (Point 6 5),
			  Rect (Point 7 3) (Point 8 6)]
	
	{- 리스트의 n번째 원소를 구하는 함수 -}
	getnth (h:t) 1 = h
	getnth (h:t) n = getnth t (n-1)
	
	{- 문제를 푸는 함수 -}
	solve = let
		p1 = getarea (getnth arg 1)
		p2 = getarea (getnth arg 2)
		p3 = getarea (getnth arg 3)
		p4 = getarea (getnth arg 4)
		
		q1 = getcap (getnth arg 1) (getnth arg 2)
		q2 = getcap (getnth arg 1) (getnth arg 3)
		q3 = getcap (getnth arg 1) (getnth arg 4)
		q4 = getcap (getnth arg 2) (getnth arg 3)
		q5 = getcap (getnth arg 2) (getnth arg 4)
		q6 = getcap (getnth arg 3) (getnth arg 4)
		
		r1 = getarea q1
		r2 = getarea q2
		r3 = getarea q3
		r4 = getarea q4
		r5 = getarea q5
		r6 = getarea q6
		
		s1 = getcap q1 (getnth arg 3)
		s2 = getcap q1 (getnth arg 4)
		s3 = getcap q2 (getnth arg 4)
		s4 = getcap q4 (getnth arg 4)
		
		t1 = getarea s1
		t2 = getarea s2
		t3 = getarea s3
		t4 = getarea s4
		
		u1 = getcap s1 (getnth arg 4)
		
		v1 = getarea u1
		
		w = p1+p2+p3+p4 - (r1+r2+r3+r4+r5+r6) + (t1+t2+t3+t4) - v1
		in
			 w
	
	{- main -}
	main = do
		h <- return solve
		putStrLn (""++show(h))

화, 2010-03-23 14:56 — kamila

I like your post its quite

I like your post its quite informative and i love to visit you again as you have done a wonderful job. i love to bookmark this site and would send it to other friends to read it and visit it to get upto date and quite interesting information 70-291 exam, i like the way you are working,keep it up, i will be here again as i get some time from 70-431 exam questions services because they make me little busy, but i would love to stuck here again 70-432 exam. Thanks for sharing nice information with us.

월, 2010-08-23 13:40 — john100998

4개의 직사각형이

4개의 직사각형이 평면에 있는데 밑변이 Testking 모두 가로축에 평행하다. 이 직사각형들이 차지하는 면적을 구하는 프로그램을 작성하시오. 이 네 개의 직사각형들은 서로 떨어져 있을 수도 있고 겹쳐 있을 수도 있다. 또한 하나가 다른 하나를 포함할 수도 있으며, 변이나 꼭지점이 겹쳐질 수도 있다. 실행 파일의 이름은 RECT.EXE로 testking VCP-410 하시오.입력형식.하나의 직사각형은 왼쪽 아래의 꼭지점과 오른쪽 위의 꼭지점의 좌표로 주어진다. 입력은 네 줄이며, 각 줄은 네 개의 정수로 하나의 직사각형을 testking 640-802 나타낸다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭지점의 x좌표, y좌표이고, 세 번째와 네 번째의 정수는 사각형의 오른쪽 위 꼭지점의 x좌표, y좌표이다. testking 350-001 단, x좌표와 y좌표는 1 이상이고 1000 이하인 정수이다.

목, 2010-08-26 19:00 — john100998

오후 시간 동안

오후 시간 동안 넉넉한 시간을 두고 자유로운 분위기에서 슬라이드로 나열만 하면서 자세한 원리를 일일이 설명한다는 느pass4sure 646-656 낌보다는 간단한 예제 등을 시연하면서 발표자가 미리 준비해 둔 소스코드나 패키지를 받아 같이 따라서 실습해 봄으로써 어떤 느낌인지를 보여 주고 관심을 유발할 수 있는 방향으로 해서 관심을 갖게 되는 pass4sure 650-251 분들은 나중에 관련 내용에 대해 더 찾아볼 수 있는 계기를 주는 그런 방향으로 갔으면 하는 계획입니다. 그래서 발표자 분들 뿐 아니라 참가하시는 분들도 가능하시다면 되도록 노트북 컴퓨터를 가지고 행사에 참여하시면 좋겠습니다.오후 시간 동안 넉넉한 시간을 두고 자유로운 분위기에서 슬라이드로 나열만 하면서 자세한 원리를 pass4sure NS0-153 일일이 설명한다는 느낌보다는 간단한 예제 등을 시연하면서 발표자가 미리 준비해 둔 소스코드나 패키지를 받아 같이 따라서 실습해 봄으로써 어떤 느낌인지를 보여 주고 관심을 유발할 수 있는 방향으로 해서 관심을 갖게 되는 분들은 나중에 관련 내용에 대해 더 찾아볼 수 있는 계기를 주는 그런 방향으로 갔으면 하는 계획입니다. pass4sure 646-046 그래서 발표자 분들 뿐 아니라 참가하시는 분들도 가능하시다면 되도록 노트북 컴퓨터를 가지고 행사에 참여하시면 좋겠습니다.

월, 2010-08-30 16:22 — john100998

오후 시간 동안

오후 시간 동안 넉넉한 시간을 두고 642-436 자유로운 분위기에서 슬라이드로 나열만 하면서 자세한 원리를 일일이 설명한다는 느낌보다는 간단한 예제 등을 시연하면서 640-816 발표자가 미리 준비해 둔 소스코드나 패키지를 받아 같이 따라서 실습해 봄으로써 어떤 느낌인지를 보여 주고 관심을 유발할 수 있는 방향으로 해서 관심을 갖게 되는 분들은 HP0-D07 나중에 관련 내용에 대해 더 찾아볼 수 있는 계기를 주는 그런 방향으로 갔으면 하는 계획입니다. 그래서 발표자 분들 뿐 아니라 참가하시는 분들도 가능하시다면 되도록 350-018 노트북 컴퓨터를 가지고 행사에 참여하시면 좋겠습니다.