7개의 댓글이 있습니다.
-
-
imyoyo -
저희팀에서는 다른 방법으로 풀었습니다. 간단히 쓰면,
지나가는 모든 점들을 순서대로 stack으로 쌓아가는데 stack에 이미 존재하는 점이 나오면 그점까지 모두 pop합니다.
최종 stack의 남은 점들에 대해 꺽이는 회수를 세면 답입니다.
한 선분당 최대 10개의 점을 가질 수 있기 때문에 점의 개수는 최대 10n개 이고,
stack에 있는 점들을 set으로 유지하면 stack에 존재하는지 여부를 log시간에 알 수 있습니다.
따라서 문제 전체가 O(nlogn) 이 됩니다.
n^2으로 풀기엔 데이터가 커서 많은 팀들이 제껴뒀던것으로 생각됩니다~
17년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
최치선
I - Turtle Graphics
I번은 실제 대회에 5팀이 푼 문제이지만, 난이도는 높은 편이 아니었습니다.
배치상 뒤에 있었고, 귀찮다는 점에서 건드리지 않은 팀이 많지 않았나 하는 생각입니다.
문제를 간단하게 설명하자면 시작점이 (0, 0)이고 lineto명령어 sequence가 들어올 때 교차하는 점이 발생하지 않게 (cycle이 존재하지 않게) cycle을 제거하고 chain 형태로 계속 그렸을 때의 선분의 수와 길이를 구하는 문제입니다.
모든 명령을 입력받고 그린 다음 최종 그림에 대한 chain을 구하는게 아닌 각 명령이 수행될 때 마다 chain상태를 유지하면서 그리는 것이기 때문에 문제가 쉬워집니다.
주요 알고리즘은 명령이 하나 들어올 때 마다 이전에 chain에 포함된 선분들을 먼저 그려진 순서대로 교차하는지 검사한 후 교차하는 선분 및 이후에 그려진 선분을 chain에서 제거 해버립니다. 그리고 교차점을 구한 후 교차한 선분의 새로운 시작과 끝을 수정하고 chain에 포함시킵니다.
주의할 점은 길이가 0인 선분일 경우 포함 시키지 않는 것과 같은 직선상에 두 선분이 놓여질 경우만 조심하면 됩니다.
상세 구현은 아래에...
17년 전