CCW 2

로테이팅 캘리퍼스의 증명

이 글을 쓰게 된 동기는 굉장히 재미있다. 증명을 원하시는 분이 있었고 누군가가 내 글을 링크해주신 것을 알게 되었지만 그 글에서는 증명이 없었고, 그래서 관심을 가지게 되었다. 어느 정도 생각해본 결과 대충 증명이 된 것 같아서 일단은 빠르게 글을 써보려고 한다. 따라서 증명이 완벽하지 않을 수도 있으며 뇌피셜일 수도, 많이 생략했을 수도 있다. 하지만 오히려 직관적으로 받아들여질 수도 있다. 댓글로 비판과 지적은 언제나 환영한다.이 글을 읽기 전에...로테이팅 캘리퍼스 설명글 stonejjun.tistory.com/42본인은 설명을 굉장히 못하기 때문에 어쩔 수 없이 설명하려면 코드와 함께 설명하는 수밖에 없을 것 같다. 위 글의 맨 마지막에 코드가 있고, 증명과정에서 그 코드를 언급을 하게 될 것 ..

BOJ 2162 - 선분 그룹

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..