dlwocks31   2년 전

소스 코드: http://boj.kr/496658765afb4b0e...

각 쥐에서 각 구멍까지 갈 수 있는지 여부를 쥐-구멍 직선경로가 어떠한 벽과 교차하는지(끝만 건드리는 케이스는 무시하고) 판단한 후, source에서 쥐까지 용량 1 에지, 쥐에서 갈 수 있는 구멍까지 용량 1 에지, 구멍에서 sink까지 용량 K 에지를 만들어 최종 플로우가 쥐의 갯수와 일치하는지를 판단하는 것까지는 잘 판단해냈는데 코드가 틀렸네요..

Dinic은 여기서 끌고 온 코드고, intersect함수는 첫번째 선을 (벡터 형식으로) A+ta, 두 번째 선을 B+sb로 두고, 구체적인 교차 여부를 반환하고 만약 교차점이 존재한다면 교차점에서의 t,s를 기록해두는 함수인데, 이 함수는 다른 문제에서 테스트를 해 보아, 기하+플로우 두 부분 코드 모두 어느 정도 정확하다고 생각하고 있었는데 4%에서 바로 틀려버리네요.. 어디서 잘못된 것일까요??

dlwocks31   2년 전

intersect함수를 double을 사용하지 않고 ccw로 다시 쓰니까 맞네요.. 실수 오차나 intersect함수의 로직 오류인듯 합니다

댓글을 작성하려면 로그인해야 합니다.