기하 1 - 백준 2477, 1002, 1004

기하에 관한 파트였다

도형을 이용한 문제였는데 꽤나 고난을 겪은 문제들이 많았다..

풀이를 참고한 문제들도 있었지만 다 풀어내긴했다.. 나중에 다시 풀어봐야지

 

https://www.acmicpc.net/problem/2477

2477번: 참외밭

ㄱ이나 ㄴ모양으로 된 직사각형이 주어지고 이 직사각형의 면적을 구하는 문제이다.

각 도형의 꼭지점이 주어지는데 점을 잇는 방향은 무조건 반시계방향이다.

시작 지점은 어느 위치든 될 수 있다.

 

이 문제를 해결하는 키포인트는 가로나 세로 모두

가장 하나의 긴 변 좌우로 다른하나의 가장 긴 변과 다른 변하나가 주어진다는 점이다.

예를들어 가로가장 긴 변 좌우로 세로 가장 긴 변과 다른 변 하나,

세로 가장 긴 변 좌우로 가로 가장 긴 변과 다른 변 하나가 주어진다.

그럼 이 것을 가지고 ㄱ모양에서 빠진 부분의 면적을 구할 수 있다.

 

입력의 첫 번째 줄에는 참외의 갯수와

다음 줄부터 방향을 나타내는 번호와 길이가 주어진다.

n = int(input()) #면적 당 참외 갯수
arr = [list(map(int,input().split())) for _ in range(6)] 
w = 0; w_idx = 0 # width의 최대 길이와 index초기화
h = 0; h_idx = 0 # height의 최대 길이와 index초기화
for i in range(len(arr)) :
    if arr[i][0] == 1 or arr[i][0] == 2 :   #저장한 list에서 방향을 결정하는 조건
        if w < arr[i][1] :		#원소값이 w보다 크면 최대 길이이므로 대입	
            w = arr[i][1]	
            w_idx = i			#해당 index저장
    else :
        if h < arr[i][1] :
            h= arr[i][1]
            h_idx = i 
#작은 사각형 구하기
subW = abs(arr[(w_idx - 1)%6][1] - arr[(w_idx + 1)%6][1])  #가장 큰 길이의 index의 앞 뒤에 위치해있으므로 추출해준다
subH = abs(arr[(h_idx - 1)%6][1] - arr[(h_idx + 1)%6][1])
result = ((w*h) - (subW*subH))*n  #가장 큰 사각형에서 작은 사각형을 제외하고 참외 갯수를 곱해주기
print(result)

#subH와 subW에서 6으로 나눈 나머지를 구하는 이유는
#가장 큰 값의 index가 6인경우 6+1을하면 7이 되어버리기 때문이다.

 

https://www.acmicpc.net/problem/1002

1002번: 터렛

이번 문제는 터렛이라는 문제인데

두 원이 주어지고 그 접점을 구하는 문제이다.

원과 원이 만나는 지점을 구하는 방법은 각 원의 반지름과 원의 중심 간의 거리만 있으면 된다.

 

해당 내용에 대한 자세한 설명은 아래링크를 참고하시길..

https://mathbang.net/101

두 원의 위치관계, 내접, 외접

import math
cases = int(input())
for _ in range(cases) :
    x1,y1,r1,x2,y2,r2 = map(int,input().split()) #두 원의 중심과 반지름을 입력받는다.
    d = math.sqrt((x2-x1)**2+(y2-y1)**2)	#두 원의 중심 사이의 거리를 구해준다
    #2개의 접점 조건
    if r1 + r2 > d and abs(r1 - r2) < d :
        print(2)
    #1개의 접점 조건 여기서 d  != 0 조건이 들어간 이유는 두 원이 같은 경우에는 무한대이므로 이를 거르기 위함
    elif d != 0 and (r1 + r2 == d or abs(r1 - r2) == d):
        print(1)
	#0개의 접점        
    elif d > r1 + r2 or d < abs(r1 - r2) :
        print(0)
    #같은 원
    elif d == 0 and r1 == r2 :
        print(-1)

이 문제를 풀때 d != 0조건을 주지 않아서 한참 헤메었다.

그래서 질문을 남겼는데 아예 같은 경우 d도 0이고 r1-r2도 0이기에 -1을 출력하는 조건이 True라는 사실을

반례로 남겨주어서 해결했다!

 

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

이 문제는 처음에 굉장히 막막했다..

두 점을 잇는 일차함수를 구해서 풀어야하나? 아니면 모든 원을 돌면서 원에 닿는지 계산해야하나? 아주 복잡했다

구글링을 통해서 출발점과 도착점 모두 원 안이나 밖에 있으면 진입과 진출을 하지 않는다는 문장을 읽고

바로 코딩해서 풀어냈다. 반대 조건도 생각해보면 풀이에 도움이 된다는 좋은 사례였다.

 

#문제 해결의 핵심은 출발점이나 도착점이 원 안에 속하면 이탈할 필요가 없고 원 밖이라면 진입할 필요가 없다.

import math
cases = int(input())

for _ in range(cases) :
    sx,sy,dx,dy = map(int,input().split()) #시작점s 도착점d
    planetN = int(input())	#행성 갯수
    result = 0		#정답을 할당할 변수 초기화
    for i in range(planetN) :
        x, y, r = map(int,input().split()) #행성 좌표 입력
        start = math.sqrt((sx-x)**2 +(sy-y)**2)	#출발점과 반지름 간 관계
        dest = math.sqrt((dx-x)**2 +(dy-y)**2)	#도착점과 반지름 간 관계
        if (start  < r and dest > r) or (dest < r and start >r) : #하나만 속하는 경우만 +1해준다
            result += 1
    print(result)

여기서 핵심은 출발점과 원점 사이의 거리가 반지름보다 작다면 해당 원 안에 있다는 뜻이고

반지름보다 크면 원 밖에 있다는 의미를 잘 이해하면 된다.

 

기하챕터까지 풀어봤는데 아직도 해결해야할 알고리즘이 무궁무진하다..

재밌으면서 힘들기도 한데 머리를 쓰는 느낌이 아주 좋다^~^