📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/1069 1069번: 집으로 은진이는 지금 (X, Y)에 있고, (0, 0)에 있는 집으로 가능한 빨리 가려고 한다. 이동할 수 있는 방법은 다음 두 가지이다. 첫 번째 방법은 걷는것이다. 걸을 때는 1초에 1만큼 움직인다. 두 번째 방법 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 1) 걷기만 하는 것이 빠른 경우(자명한 경우) - 직선 거리(= 걷기만 해서 도착하는 시간) =D인 경우(걸음 자체가 점프보다 빠름) 최소 도달 시간 = 직선 거리 2) 점프만 하는 것이 빠른 경우(자명한 경우) - 직선 거리가 D의 정수 배인 경우 최소 도달 시간 = ((직선 거리)//D)*t 3) 걷기와 ..
📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 제 2 코사인 법칙을 활용해 각도를 구해서 넓이를 구하는데 사용 ''' from math import dist, pi, acos, sin input = open(0).readline def solution(): x1, y1, r1, x2, y2, r2 = map(float, input().split()) if (x1-x2)**2 + (y1-y2)**2 >= (r1+r2)**2: # 겹치지 ..
📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 선분 교차1의 문제에 한 선분의 끝 점이 다른 선분 위에 있는 경우도 교차하는 것으로 포함하는 문제이다. 일직선에 놓인 세 점의 외적은 0이므로 이 조건을 추가해주자. 이때 두 선분이 일직선 위에 있는 경우에는 모두 외적이 0이지만 겹치지 않는 경우도 있다. 기준 선분을 바꿔도 외적 벡터 쌍의 곱이 모두 0인 경우에 일직선이기에 이 경우를 추가 확인하자. ''' input = ope..
📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 벡터 외적을 활용한 CCW 알고리즘을 활용하여 구할 수 있다. 하나의 기준 선분과 기준 선분의 한 점과 다른 선분의 각 끝 점이 이루는 두개의 벡터 쌍의 외적을 각각 구한다. 이 두 외적 벡터가 각각 다른 방향이라면 교차를 하게된다.(두 외적 벡터의 곱이 음수) 그러나 교차하지는 않으나 이루는 각의 방향이 다른 경우가 있다. 이런 경우라면 기..
📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 벡터의 외적 계산을 통해 면적을 구하는 문제이다. 각 꼭지점의 좌표를 통해 넓이를 구하는 신발끈 공식을 활용해 풀 수 있다. ''' input = open(0).readline def solution(): n = int(input()) xs,ys = [],[] for _ in range(n): x,y = map(int,input().split()) ..
📌문제 출처 백준 단계별 문제풀이 : 기하2 https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 선분의 진행 방향이 어느 방향으로 바뀌었는지 확인하는 문제이다. 두 벡터의 외적을 구하는 공식을 활용한 CCW(counter clock wise) 알고리즘으로 풀 수 있다. 두 벡터의 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이와 같고 방향은 두 벡터..
📌문제 출처 백준 단계별 문제풀이 : 유니온 파인드 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' find 함수로 해당 노드와 이어진 최소 노드를 찾아 parents에 넣고, union 함수로 같은 parents를 만들어준다. 두개 노드씩 입력값을 받으면서 두 노드의 parents가 이미 같다면 사이클이 처음으로 완료되는 지점이다. 두 노드의 parents가 다르다면 union을 계속 진행한다. ''' in..
📌문제 출처 백준 단계별 문제풀이 : 유니온 파인드 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' union-find 유형의 문제에서 parents는 list 형태로 만들었으나, 이번에는 입력값이 문자열이므로 dictionary 형태로 만든다. 매번 친구 관계 입력값을 받을 때마다 Union을 실행하여 한 쪽으로 parents를 맞춰주고 상위 parents인 쪽에 친구의 수를 더해준다. * 수 형태에선..
