[백준/python] 기하 1 전체 풀이(13단계)

 

목차

 

직사각형에서 탈출(#1085)

• Problem

한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

 

• Hint

2차원 좌표내 거리 = del x + del y

테두리까지의 거리를 어떻게 표현해야할까 생각해보자

 

• Solution

기하를 이용한 풀이

x,y,w,h=map(int,input().split())
print(min(min(x,w-x),min(y,h-y)))

테두리까지의 최소값은 delx와 y 중에 최소값을 고르면 된다

---

 

네 번째 점(#3009)

• Problem

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

 

• Hint

 

 

• Solution

기하를 이용한 풀이

x=[]
y=[]
res=[]
for i in range(3):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)

if x[0]==x[1]:
    res.append(x[2])
else:
    if x.count(x[0])==1:
        res.append(x[0])
    else:
        res.append(x[2])


if y[0]==y[1]:
    res.append(y[2])
else:
    if x.count(y[0])==1:
        res.append(y[0])
    else:
        res.append(y[2])

print(*res)

결국 x y 각각 두쌍이 존재하면 된다. 식을 받아올때 if 로 이미 a 가 리스트 내에 존재하는지 여부를 확인하는 조건문을 사용해도 될것이다.

 

식이 복잡하여 숏코딩 란을 보았다.

 

---

XOR을 이용한 풀이

x=y=0

for _ in range(3):
	a,b=map(int,input().split())
    x^=a
    y^=b
    
print(x,y)

XOR의 개념은 떠올렸지만 XOR을 이용하면 정수도 이렇게 결과가 나올줄 몰랐다

어차피 출력값은 완전한 한쌍을 제외한 정수이기 때문에 XOR을 사용하면 같은 정수끼리는 x^x = 0 이 될테고 여기에 순서 상관없이 x^y^x , y^x^x, x^x^y 들어오게 되어도 출력값은 y이기 때문에 간단하게 나오게 된다.

 

나중에 풀이에 좋은 팁이 될 것 같다.

---

 

 

직각삼각형(#4153)

• Problem

과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.

 

• Hint

각 변을 주어준다고 했지 맨 뒤에 인자가 가장 긴 변이라고는 안한것을 잘 봐야한다.

 

• Solution

기하를 이용한 풀이

a=b=c=1
res=[]
while a+b+c!=0:
    a,b,c=sorted(map(int,input().split()))
    if a*a+b*b==c*c:
        res.append('right')
    else:
        res.append('wrong')

print(*res[:-1],sep='\n')

sorted를 이용해 오름차순으로 바꿔주었다.

 

---

 

 

참외밭(#2477)

• Problem

시골에 있는 태양이의 삼촌 댁에는 커다란 참외밭이 있다. 문득 태양이는 이 밭에서 자라는 참외가 도대체 몇 개나 되는지 궁금해졌다. 어떻게 알아낼 수 있는지 골똘히 생각하다가 드디어 좋은 아이디어가 떠올랐다. 유레카! 1m2의 넓이에 자라는 참외 개수를 헤아린 다음, 참외밭의 넓이를 구하면 비례식을 이용하여 참외의 총개수를 구할 수 있다. 1m2의 넓이에 자라는 참외의 개수는 헤아렸고, 이제 참외밭의 넓이만 구하면 된다. 참외밭은 ㄱ-자 모양이거나 ㄱ-자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형이다. 다행히도 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향이었다. 밭의 한 모퉁이에서 출발하여 밭의 둘레를 돌면서 밭경계 길이를 모두 측정하였다. 예를 들어 참외밭이 위 그림과 같은 모양이라고 하자. 그림에서 오른쪽은 동쪽, 왼쪽은 서쪽, 아래쪽은 남쪽, 위쪽은 북쪽이다. 이 그림의 왼쪽위 꼭짓점에서 출발하여, 반시계방향으로 남쪽으로 30m, 동쪽으로 60m, 남쪽으로 20m, 동쪽으로 100m, 북쪽으로 50m, 서쪽으로 160m 이동하면 다시 출발점으로 되돌아가게 된다. 위 그림의 참외밭 면적은 6800m2이다. 만약 1m2의 넓이에 자라는 참외의 개수가 7이라면, 이 밭에서 자라는 참외의 개수는 47600으로 계산된다. 1m2의 넓이에 자라는 참외의 개수와, 참외밭을 이루는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 순서대로 주어진다. 이 참외밭에서 자라는 참외의 수를 구하는 프로그램을 작성하시오.

 

• Hint

내가 생각해낸 풀이의 경우에는 index의 쓰임에 주의 했어야했다.

 

• Solution

기하의 특징을 이용한 풀이

k = int(input())
vat=[]
for i in range(6):
    n,l = map(int,input().split())
    vat.insert(i,[n,l])
    vat.insert(i+6,[n,l])

leng= list(i[1] for i in vat)

atd =0
btd =0
cnt=0
for i in vat:
    if (i[0]==1 or i[0]==2) and i[1]>atd: // 가로
        amax=i[1]
        aindex=cnt
        atd=amax
    if (i[0]==3 or i[0]==4) and i[1]>btd: // 세로
        bmax=i[1]
        bindex=cnt
        btd=bmax
    cnt+=1

area = amax*bmax
minl = min(aindex,bindex)

if abs(aindex-bindex)==1: 	//두 인덱스의 차가 1인 경우 즉, 연속해서 나타나는 경우
    print((area-(leng[minl+3]*leng[minl+4]))*k)
else:						//두 인덱스가 떨어져서 나타나는 경우 0과 5
    print((area-(leng[minl+2]*leng[minl+3]))*k)

한쪽이 패인 육각형의 모습이라고 했으니 어디에서 시작하던간에 가로 세로 최대 길이변이 서로 맞닿는 꼭짓점의 반대에 위파인 사각형이 위치하고 있다.

 

따라서 이 기본적인 틀을 잡고 원형 큐를 구현할까 생각하려다가 그냥 리스트에 저장할때 두 번 저장하게 만들었다. 이렇게만 해주어도 원형 큐를 많이 사용해봤자 인덱스 9까지 밖에 사용하지 않기 때문이다.

 

그 다음 index를 이용하지 않고 (긴 변의 길이가 각각 다를경우에는 상관이 없는데 같은 경우에 index가 같은 값을 가지게 된다.)

+가로인지 세로인지 조건문을 넣어주어도 되지만 그냥 cnt 변수를 하나 더 추가해주었다.

 

이후에 인덱스가 붙어있는 경우와 아닌 경우로 나누어 반대편의 사각형의 두 값을 뽑아내어 계산하였다.

---

기하의 특징을 이용한 풀이

 

들어온 변의 길이와 그 다음 변을 무조건 곱한 후에 전체에 그 곱의 쌍중에 가장 큰 값을 두번 빼준다.

 

 

택시 기하학(#3053)

• Problem

19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |y1-y2| 두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다. 따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다. 원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합 반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.

 

• Hint

파이썬에서의 파이는 from math import pi 를 사용하면 사용가능하다.

 

• Solution

파이를 이용한 풀이

from math import pi

r = int(input())
print(r*r*pi)
print(((r*2)**2)/2)

---

 

 

터렛(#1002)

• Problem

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다. 다음은 조규현과 백승환의 사진이다. 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

 

• Hint

원의 접점의 개수를 센다고 생각하면 쉽게 풀린다.

• Solution

기하를 이용한 풀이

from math import sqrt

res=[]
n = int(input())
for i in range(n):
    ax,ay,ar,bx,by,br=map(int,input().split())
    dis=sqrt((ax-bx)**2+(ay-by)**2)
    l=max(ar,br)
    s=min(ar,br)

    if dis==0:
        if ar==br:
            res.append('-1')
        else:
            res.append('0')
    elif l-s>dis:
        res.append('0')
    elif l+s<dis:
        res.append('0')
    elif l+s==dis:
        res.append('1')
    elif l-s==dis:
        res.append('1')
    else:
        res.append('2')
    
print(*res,sep='\n')

접하지 않는 경우 3가지

한점에서 접하는 경우 2가지모두 겹쳐져서 무한대인 경우 1가지나머지는 전부 2가지인 경우로 쉽게 해결 가능하다.

---

 

어린 왕자(#1004)

• Problem

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다. 빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다. 위와 같은 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자. 행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.

 

• Hint

문제의 설명이 어렵다고 느낄수 있지만 결국엔 각 위치가 행성 안에 들어와 있는지를 살펴보면 된다

 

• Solution

기하를 이용한 풀이

def starin(x,y,lx,ly,sx,sy,sr):
    if (x-sx)**2+(y-sy)**2<sr**2 and (lx-sx)**2+(ly-sy)**2>=sr**2:
        return 1
    else:
        return 0

t =int(input())
res=[]

for i in range(t):
    stx,sty,edx,edy = map(int,input().split())
    n=int(input())
    cnt=0
    for j in range(n):
        sx,sy,sr = map(int,input().split())
        cnt+=starin(stx,sty,edx,edy,sx,sy,sr)
        cnt+=starin(edx,edy,stx,sty,sx,sy,sr)
    res.append(cnt)
print(*res,sep='\n')

starin 이라는 함수를 만들어서 문제를 풀어보았는데 문제의 조건중에 또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다. 라는 조건이 있기 때문에 조건문을 출발점이 행성의 안에 존재하되 도착점이 행성에 안에 있거나 겹치는 경우를 제외하여 개수를 cnt를 증가시킨다. 라는 조건을 이용하였다.

---

 

 

하키(#1358)

• Problem

지난주에, 민식주식회사는 IIHF(International Ice Hockey Federation)로부터 긴급한 전화를 받았다. IIHF는 같은 팀이 링크안에 너무 많으면 알람이 울리는 시스템을 설치해달라고 요청했다. 시스템은 다음과 같이 3개의 부분으로 이루어진다. 디지털카메라가 링크의 사진을 매 1초마다 찍는다. 디지털카메라가 찍은 사진에서 각 선수의 위치를 뽑아낸다. 하키 링크 안에 같은 팀 선수가 총 몇 명인지 계산한다. 하키 링크는 (X, Y)가 가장 왼쪽 아래 모서리인 W * H 크기의 직사각형과, 반지름이 H/2이면서 중심이 (X, Y+R), (X+W, Y+R)에 있는 두 개의 원으로 이루어져 있다. 아래 그림을 참고한다. 선수들의 위치가 주어질 때, 링크 안 또는 경계에 있는 선수가 총 몇 명인지 구하는 프로그램을 작성하시오.

 

• Hint

중학교 시절의 범위 나누기를 생각해보자

 

• Solution

기하를 이용한 풀이

def playerin(x,y,gw,gh,gx,gy):
    if x>=gx and x<=gx+gw and y>=gy and y<=gy+gh:
        return 1
    elif ((gx-x)**2+((gy+gh/2)-y)**2)<=(gh/2)**2:
        return 1
    elif ((gx+gw-x)**2+((gy+gh/2)-y)**2)<=(gh/2)**2:
        return 1
    else:
        return 0

gw,gh,gx,gy,p = map(int,input().split())
cnt=0

for i in range(p):
    x,y=map(int,input().split())
    cnt+=playerin(x,y,gw,gh,gx,gy)
print(cnt)

아마도 구현 방법은 다들 머리속에 있지만 그것을 코딩으로 짜기까지의 과정이 어려운것 같다.

사각형 부분과 반원 두부분으로 나누어주었고 if elif 특성상 상위의 조건이 맞지않으면 다음 조건으로 넘어가는 특성을 가지고 있기 때문에 이렇게 수식을 짜도 상관이 없다.