상위 99.99%의 PS

Half Convex Hull 문자 그대로 반껍질이다. 볼록 껍질을 구할 때처럼 하면 된다. BOJ 14745 - Jeong Lab 문제를 다르게 바꾸면 다음과 같다. 용액을 하나의 좌표로 보고, 점 $Q(c_i,d_i)$가 반껍질 내에 존재하는 지의 여부를 확인하기. 이는 매우매우 간단하다. lower_bound를 사용하여, 점 $P_l,P_{l+1},Q(c_i,d_i)$의 ccw를 확인해주면 된다. 반껍질에 점 추가하기 그러나 이 문제에서 요구하는 것이 하나 더 있다. 반껍질 내에 점이 존재하지 않는다면, 이 반껍질에 점을 추가해주어야 한다. 그리고 반껍질을 다시 구성해야 한다. 먼저, 점이 들어갈 위치를 구한다. lower_bound를 사용하여 위치를 찾을 수 있다. 그 다음, 한..

Convex Hull 2차원 평면 위의 점들을 모두 포함하는, 넓이가 최소인 볼록 다각형을 구해보자. 이는 볼록 껍질이라는 것을 구하면 해결된다. 볼록 껍질을 구하는 것은 여러 방법이 있지만, 나는 반껍질 두 개를 구하는 방식을 선호한다. 한 쪽 반껍질을 구하고, 다른 반껍질은 반대로 구하면 되기 때문이다. (저번 게시글에서 볼록 껍질을 구할 때 각도 정렬이 필요하다고 했지만..) 이 방법은 각도 정렬을 하지 않아서 편하다. 일단 반껍질을 구하기 전, x좌표, y좌표 순으로 증가하도록 점들을 정렬하자. 점들을 정렬했다면, 이제 볼록 껍질을 만들 수 있다. 점들을 스택에 넣으며, 마지막 세 점의 방향이 반시계 방향이 되도록 적절히 스택에서 pop을 하면 된다. 글로 쓰는 것은 내가 봐도 설명이 구리기 때문..

기하를 싫어하는 이유 ps를 하는 사람 중 기하를 싫어하는 사람은 꽤나 된다. 물론 나 또한 그랬기에, 기하를 싫어하는 이유가 무엇인지는 대충 알고 있다. 내가 기하를 싫어했던 이유는 이렇다. 1. 코드가 깔끔하게 나오지 않는 편이다. 2. 실수 연산이 까다롭다. 3. 예외처리가 많다. 1번의 경우, 함수를 최대한 많이 사용하면 그나마 깔끔해진다. 사소한 계산이라도 함수를 사용해서 따로 빼주는 게 눈버깅에도 편하다. 2번의 경우, 최대한 정수로 계산하는 편이 낫다. 근데 보통의 문제들은 double형으로 그냥 계산해도 정답이 나올 정도의 오차 범위를 주기 때문에 이를 신경 쓸 일은 그렇게 많지 않...다. 3번의 경우를 내가 진짜 싫어했다. 노트에 대충 끄적이면 그대로 코딩을 하는 매우 나쁜 습관이 있어..

들어가기 전에, 코드는 파이썬으로 작성했으니 참고했으면 좋겠다. 어자피 작동 원리는 같으니 문제는 안 된다. https://www.acmicpc.net/problem/16911 16911번: 그래프와 쿼리 첫째 줄에 정점의 개수 N(2 ≤ N ≤ 100,000)과 쿼리의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제를 풀어보자. 처음에는 어떤 두 정점도 연결되지 않은 상태이고, 다음 쿼리들을 수행하는 문제이다. 1번 쿼리: 두 정점을 연결하는 간선을 추가한다. 2번 쿼리: 두 정점을 연결하는 간선을 제거한다. 3번 쿼리: 정점 u에서 v로 가는 경로의 존재 여부를 출력한다. 2번 쿼리가 없다면, 단순하게..

https://www.acmicpc.net/problem/17474 17474번: 수열과 쿼리 26 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 L R X: 모든 L ≤ i ≤ R에 대해서 Ai = min(Ai, X) 를 적용한다. 2 L R: max(AL, AL+1, ..., AR)을 출력한다. 3 www.acmicpc.net [알고리즘 분류] Segment tree beats greedev에게 세그비츠가 웰논인지 물어봤는데, 다음과 같은 답변을 받았다. (수쿼 25~30은 모두 세그비츠를 사용한다고 한다.) 나는 정말 무식하지만, 최대한 열심히 설명해보도록 하겠다. 나보다 설명을 몇십배는 잘 해둔 글이 수두룩하기 때문에, 나의 글로..