https://www.acmicpc.net/problem/25315
문제요약
- 선분들이 주어짐. 그들끼리 교차함. 어떤 세점도 한 직선에 있지 않음
- 선분을 지워나갈때 비용이 발생 : 선분의 비용(w) * (겹치는 점 + 1)
- 선분을 지우면 없어지고, 계속 진행
- 비용을 가장 작게
- N 2500, 좌표 범위 +-10^9
접근법
- ccw를 이용해 선분 교차 판단은 가능함
- ccw : A, B, C 를 이었을때 시계반대방향이면 > 0, 시계방향이면 < 0, 일직선이면 0
- 다행히 세 점이 한 직선에 없어서 판단이 편함
- 선분 AB에 대해 다른 선분의 점 C, D가 서로 반대 방향에 있고, 선분 CD에 대해서서도 동일하면 됨
- 만나는 두 선분(p, q)중 어느 한쪽을 먼저 지울텐데
- p를 먼저 지우면 Wp발생, q를 먼저 지우면 Wq 비용 발생 => 비용이 적은 것 먼저 지우면 될 것 같음
- 꼬이는 경우는 발생하지 않을까?? => 정수 비교에서 꼬이는 일은 발생하지 않으므로 괜찮음
- 진짜 이 논리로 가능 한가??
- 일단 (만나는 점 + 1) 이므로 자신의 비용은 모두 발생함 : W1 + W2 + ... Wn
- 1 선분을 지울때 발생하는 비용 : W1 * 만나는 점(4, 11, 20, 21 점이라고 하자)
- A 선분을 지움으로써 아끼는 비용 : W4, W11, W20, W21
- W1*4 - (W4 + W11 + W20 + W21) 가 작아야 유리
- 점점 확장하다 보면 W1 < Wx 가 되어야 유리 => 정렬
newbieski