Toolofv 님의 블로그

백준 - 2162 선분 그룹첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.www.acmicpc.net문제N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한..

백준 - 20149 선분 교차 3첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.www.acmicpc.net 문제해결방법 -   1. 사선공식(신발끈 공식)을 이용하면 주어진 3점의 좌표 방향에 따라 1, 0, -1을 출력한다는 것을 알 수 있다. 1) (x1, y1) (x2, y2) 직선에서 각 점 (x3, y3) 과 (x4, y4)을 사선공식으로 돌린다. 결과를 곱했을 때  0, -1의 경우만 교점이 있을 가능성이 있다.2) (x3, y3), (x4, y4) 직선에서도 각 점 (x1, y1) 과 (x2, y2)을 사선공식으로 돌린다. 위와 같다. 2. 위 결과가 둘 다 0, -1인 경우만 본다. 예외적으로 기울기가 같을 때,..

백준 - 25308 방사형 그래프첫째 줄에 8개의 능력치를 나타내는 정수 $a_1, a_2, \cdots , a_8$가 공백으로 구분되어 주어진다. ( $1 \leq a_i \leq 10^4$)www.acmicpc.net  문제해결방법 - (구글링, 챗GPT 참조) 1. 신발끈 공식이라 일컬어지는 사선공식을 활용한다. 이 사선공식은 좌표로 주어지는 삼각형의 넓이를 구하는 공식인데, 절댓값을 취하기 전, 계산한 결과가 음수냐 양수냐에 따라 p1(x1, y1), p2(x2, y2), p3(x3, y3)의 순서로 선을 긋는다고 할 때 시계방향인지, 반시계방향인지 알 수 있다. (음수면 시계방향, 양수면 반시계방향) 이 문제에서 방향을 체크하는 것으로 연동되어 알 수 있는 것은 삼각형이 p2(x2, y2)에 따..