라인스위핑5 BOJ 2261 - 가장 가까운 두 점 (라인스위핑) https://www.acmicpc.net/problem/2261 https://www.acmicpc.net/blog/view/25 위 링크의 백준님이 설명해주신 방법 리뷰 좌표평면 위에 최대 n개의 좌표 x,y가 주어질 때, 가장 가까운 두 점의 거리의 제곱을 구해라 (n> p[i].first >> p[i].second; sort(p, p + n); ll st = 0, ans = 2e18; set cand; cand.insert(p[0]); for (ll i = 1,x,y; i ans) { cand.erase(p[st]); st++; } else.. 2020. 5. 19. BOJ 14463 - 소가 길을 건너간 이유 9 (세그트리, 라인스위핑) https://www.acmicpc.net/problem/14463 distinct한 좌표를 갖는 교차하는 선분쌍의 '개수' nlogn에 구하기 참고: n^2에 모든 교차하는 선분쌍을 하나하나 들여다 보는 로직 https://suuntree.tistory.com/112 선분i를 처음부터 순차로 보면서, 선분 i의 범위가 [lo,hi]라면, hi를 세그먼트트리에서 1 올리는 update를 해준다. 그러면 0~i-1번 선분과 선분 i가 교차하는 쌍의 개수는 psum[i끝점] - psum[i시작점]이다. 다시말해서, 0~i-1번 선분 중에 선분 i[lo,hi]와 교차하는 선분의 개수는, 끝나는 점이 [lo,hi]에 속하는 선분의 개수이다. (선분i에 포함되는 선분은 i+1이후이므로 신경쓰지 않는다.) cons.. 2020. 2. 29. BOJ 17026 - Mountain view (라인스위핑) https://www.acmicpc.net/problem/17026 전체선분의 개수에서 어떤 선분에 완전히 포함되는 선분의 개수를 뺀 나머지를 구해라. (입력 x,y면 선분은 [x-y, x+y]) 선분 [l,r] n개에 대해 l기준으로 오름차순 정렬하되 l이 같다면 r기준 내림차순 정렬한다. 선분들을 차례로 돌면서 r의 최대값을 mx에 유지하고 mx보다 크다면 ans++해준다. 어떤 선분에 포함되는 선분의 개수를 구하고싶다면? n-ans int n; P p[MAX]; int main() { FAST; cin >> n; for (int i = 0,x,y; i > x >> y; p[i].first = x - y, p[i].second = x + y; } sort(p, p + n.. 2020. 2. 24. 라인스위핑 새로운 유형 만날때마다 업데이트 예정 최대로 교차하는 선분의 개수. O(nlogn) https://suuntree.tistory.com/103 2번유형 (그리디) 모든 교차하는 두 쌍의 선분에 대한 질의. O(n^2) https://suuntree.tistory.com/112 어떤 선분에 포함되는/포함되지 않는 선분의 개수. 정렬후 O(n) https://suuntree.tistory.com/190 2019. 12. 29. 이전 1 2 다음
