N수매화검법

• 베기경로가 교차하는 곳마다 내공이 소모된다. 선분 교차 판정 알고리즘을 사용해서 처리한다.
• 가중치가 작은 검법을 먼저 사용하는 것이 유리하다. 선분을 가중치순으로 정렬한다음에, 다른 선분들과 교차 여부를 계산해서 내공을 계산해주면 된다.
• 굳이 선분을 정렬해서 처리할 필요 없이, 그냥 두 선분의 교점마다 작은 가중치를 더해주어도 결과는 동일하다.
  • 코드는 이쪽이 더 간단할수도 있는데, 속도면에서는 매번 두 가중치중 작은것을 계산해주는 것보다, 그냥 정렬을 해놓고 처리하는 편이 약간더 빨랐다.
• 모든 페어에 대해서 선분 교차 여부를 구하고 거기에 따라서 내공을 업데이트 해줘야 한다. 그래서 시간 복잡도는 O(n^2).
• 파이썬에서는 시간이 꽤 빡빡하다. 처음에 제출했을때에는 PyPy로도 800ms 정도가 나왔었다. python으로 통과될 정도로 시간을 단축시키기 위해서 꽤나 열심히 최적화를 해야 했다.
  • 세 점이 colinear한 경우는 주어지지 않는다는 조건이 있다. 이를 이용해서 선분교차판정 로직을 좀더 심플하게 할수 있다. 그리고 CCW 여부를 판정하는 것을 함수를 만들지 않고 그냥 인라이닝시키면 아래처럼 쓸수 있다.

    • (((ay2 - ay1) * (bx1 - ax2) > (ax2 - ax1) * (by1 - ay2)) !=
         ((ay2 - ay1) * (bx2 - ax2) > (ax2 - ax1) * (by2 - ay2))) and
        (((by2 - by1) * (ax1 - bx2) > (bx2 - bx1) * (ay1 - by2)) !=
         ((by2 - by1) * (ax2 - bx2) > (bx2 - bx1) * (ay2 - by2)))

  • 같은 a선분과 다른 선분들을 비교할 경우, ay2 - ay1 과 ax2 - ax1이 계속 반복되므로 이 값을 한번만 계산해두고 재활용하면 시간이 많이 단축된다.
  • 이렇게 해서 아슬아슬하게 1800ms 정도로 통과했다 (제한은 2000ms)

"""Solution code for "BOJ 25315. N수매화검법".

- Problem link: https://www.acmicpc.net/problem/25315
- Solution link: http://www.teferi.net/ps/problems/boj/25315

Tags: [Geometry] [Greedy]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    line_segments = []
    for _ in range(N):
        sx, sy, ex, ey, w = [int(x) for x in sys.stdin.readline().split()]
        line_segments.append((w, sx, sy, ex, ey, ex - sx, ey - sy))
    line_segments.sort(reverse=True)
    answer = 0
    for _ in range(N):
        w, ax1, ay1, ax2, ay2, axdiff, aydiff = line_segments.pop()
        for _, bx1, by1, bx2, by2, bxdiff, bydiff in line_segments:
            if (((aydiff * (bx1 - ax2) > axdiff * (by1 - ay2)) !=
                 (aydiff * (bx2 - ax2) > axdiff * (by2 - ay2))) and
                ((bydiff * (ax1 - bx2) > bxdiff * (ay1 - by2)) !=
                 (bydiff * (ax2 - bx2) > bxdiff * (ay2 - by2)))):
                answer += w
        answer += w

    print(answer)


if __name__ == '__main__':
    main()