선분교차판정1 백준 25315 / C++ https://www.acmicpc.net/problem/25315 25315번: N수매화검법 화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다. N수매화검법은 2 www.acmicpc.net [ 풀이 ] 선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 서로 교차하는 것끼리 묶었다고 해보자. 묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까) 벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. (그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨) 이제 구현해보.. 2022. 8. 8. 이전 1 다음