https://www.acmicpc.net/problem/2162문제조건N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 그룹의 수, 가장 크기가 큰 그룹에 속한 선분의 개수를 구하시오.접근방법 선분끼리 만나는 경우를 하나하나 모두 체크를 해줘야하는지 생각해봤다.그리고 선분끼리 교차하는 건 코드로 어떻게 나타낼지 감이 안와서 검색을통해 알아냈다.https://bowbowbow.tistory.com/17 [기하] 외적을 이용해서 선분과 선분의 교차점 구하기[기하]외적을 이용해서 선분과 선분의 교차점 구하기 목차 [기하]외적을 이용해서 ..

https://www.acmicpc.net/problem/2254 문제조건 감옥의 좌표 (px,py)가 주어진다.담 기둥의 좌표들이 주어진다.감옥과 담 기둥은 일직선상에 위치할 수없다.각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다겹치지 않는 최대의 중첩된 담의 겹 수?접근방법 처음보는 유형의 문제라 생각만 2시간이상하다가 검색을 통해 도움을 얻었다,,,,역시 구현이나 어떤 알고리즘을 쓰는가 보다는 기하학적으로 접근해야하는 문제였다.정말 오랜만에 다시 보는 벡터의 외적이 쓰인다니,,, 역시 배운게 다 쓰이긴 한다. Convex Hull 알고리즘 이 문제에서 사용된 알고리즘이다.convex hull이 그래서 대체 뭐냐? 2차원 좌표 ..