본문 바로가기

전체 글

CCW와 CCW를 이용한 선분 교차 판별 PS에서 종종 이용되는 선분 교차 여부 판별을 CCW를 이용하여 비교적 간단(?)하게 할 수 있는 방법을 소개하려고 합니다. 그 전에 우선 CCW에 대하여 이야기 해보겠습니다. CCW는 Counterclockwise의 약자로 풀어 해석하면 그냥 반시계 방향입니다. PS에서의 CCW는 세 점에 대한 방향성을 나타냅니다. CCW의 return 값은 보통 세가지 경우입니다. 1. 반시계 방향인 경우 2. 시계 방향인 경우 3.세 점이 평행한 경우 이렇게 세가지 경우로 분류되며 CCW는 삼각형의 면적을 구하는 공식+벡터를 이용하여 구해지게 됩니다. 해당 식에서 S가 0보다 크면 반시계 방향 S가 0보다 작으면 시계 방향 S가 0이면 세 점이 평행합니다. 이를 소스코드로 작성하면 아래와 같습니다. 1234567i.. 더보기
2017 ACM-ICPC Daejeon Regional 인터넷 예선 후기 2016년 3월 PS라는걸 처음 알게 되고 ,2016년 8월 처음으로 이걸 제대로 공부해 봐야겠다는 생각이 들었고, 2016년 12월 블로그 이름을 ACM-ICPC 상 탈 사람이라고 달아버리고, 마침내 어제 목표로 하던 ACM-ICPC 대전 리저널 본선으로 가는 티켓을 따기 위한 인터넷 예선을 치루게 되었다. SCPC, 카카오 코드 페스티벌 등.. 이제 대회 경험이 꽤 생겼지만 이렇게 가슴이 떨린적은 처음인것 같다. 처음부터 이 대회를 목표로 공부를 시작하였으니 그런듯 하다 .. 2시에 대회가 시작된 뒤 등록 문제가 바뀐 걸 인지 못해서 엉뚱한 답안을 작성할 뻔 했지만 팀원들이 잘 지적해주어서 제대로 고쳐서 냈다. 초반 스퍼트는 굉장히 좋았다.. 아니 솔찍히 기대 이상이였다. 우리가 4문제를 풀어낸 시간.. 더보기
좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 더보기

티스토리툴바