sort(a, a+n, [&](const pnt &a, const pnt &b){if((pi(a.x, a.y) > pi(0, 0)) ^ (pi(b.x, b.y) > pi(0, 0))) return pi(a.x, a.y) > pi(b.x, b.y);if(ccw(a, b) != 0) return ccw(a, b) > 0;return hypot(a) < hypot(b);});앞문제를 풀다가 발견한 코드. 1 2 3 4 사분면에 상관없이 각도정렬을 할 수 있다. + 5.21 업데이트. 각도가 같을 경우 거리순으로 정렬한다. (hypot(p) = p.x^2 + p.y^2, pi = make_pair) + 2017.8.14 업데이트. 코드 길이를 많이 줄였다.
1. Antenna http://amugelab.tistory.com/entry/problem-solving-20160130 에 있는 phone cell 문제 + binary search. https://github.com/koosaga/olympiad/blob/master/CEOI/ceoi06_antenna.cpp 2. Queue N이 작은 케이스에서 시작하자. 이 때는 linked list의 요령으로 문제를 풀 수 있다. prev(i) = i번의 왼쪽 원소, next(i) = i번의 오른쪽 원소라고 했을때, 초기값은 i-1, i+1로 가득 차 있고, 질의가 들어왔다면, 일단 A를 삭제하고, B의 앞에 A를 박으면 된다. 방법은 생략. 이러한 식으로 처리한 후, 후에 배열의 값을 모두 저장해놓고, 그냥..
(LCD Soundsystem, 2005)
https://www.acmicpc.net/problem/12010 이해가 안가면 이 글과 참고해서 보면 좋다 : http://usaco.org/current/data/sol_landscape_platinum_open16.html여담으로 이 문제는 KOI 2005 소방차와 상당히 유사한 문제다. 같이 보면 좋을 듯 하다. http://koistudy.net/?mid=prob_page&NO=313 1. O((NK)^2)dirt의 개수만큼 위치를 저장해 놓은 수열을 펴보자. 예를 들어 3, 1, 5, 1과 같이 수열이 주어지면 0, 0, 0, 1, 2, 2, 2, 2, 2, 3과 같은 형태로 수열을 바꾸는 것이다.수열 A, B가 있을 때 진행하는 연산에 대해서 다시 생각해 보면* 1. 추가 -> 수열 B에 ..
https://www.acmicpc.net/problem/3319한동안 글을 한꺼번에 썼었는데 나눠 쓰는 게 여러모로 나을 듯 하다. 앞으로 그런 방향으로 바꿔나가려고 함.언제봐도 신기한 harbingers 문제를 다시 리뷰하려고 한다. O(N^2)dp[i] = Min(dp[j] + (depth(i) - depth(j)) * V[i]) + S[i] for all j = (ancestor of i) 이다. Special Cases : Line O(NlgN) 일직선에서 이 문제는 아주 유명한 컨벡스 헐 트릭이다. (depth(j), func(j)) 라는 형태의 일차함수가 순서대로 들어오고, V[i] 쿼리를 이진 탐색으로 처리해 주면 된다. 이해가 안가면 여기서 멈추고, http://dyngina.tistor..
Soap Time (CF 118E) http://codeforces.com/contest/185/problem/E 일단 45도 돌려서 chebyshev distance로 생각하고, 지하철역이 없을 때에 대한 corner case를 처리해주자. 먼저 minsub[i] = (i번 정점에서 가장 가까운 임의의 지하철역까지의 거리) 를 정의하고, 구한 후 시작하자. 시간 제한이 넉넉하기에 아무 방법이나 썼는데, 난 2d range tree를 짠 후 parametric search를 돌리는 방식으로 O(nlg^3n)에 해결하였다. 문제 해결에 있어서는 최댓값을 최소화하기 때문에 직관적으로 parametric search가 떠오른다. parametric search를 구현하는 것이 가장 어려운 부분이다. 일단 답이..
1. 지우개 https://www.acmicpc.net/problem/11881 Solution 1 : dp[i][j] = A(a1) < A(a2) ... < A(aj) N - K개의 점을 지났다라고 정의하겠습니다. dp[i][j] = i번 점을 j번째로 지났다 라고 정의하면, 다음과 같은 점화식을 유도할 수 있습니다.dp[i][j] = Min(dp[i-1][k] + |Xj - Xk| + |Yj - Yk|) for all 1 = 2) 시간 복잡도는 O(N^3). 3. 신기한 키보드https://www.acmicpc.net/problem/1796 고정된 알파벳에 대해서 생각해보면 각각의 알파벳의 위치는 딱히 중요하지 않습니다. 'a'를 값으로 가지는 가장 왼쪽 / 오른쪽 만 찍고 오면 되니까요.dp[i][..
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=249좀 많이 입풀이라... 가려 듣길 부탁한다 ㅠㅠ D : Travel검증되지 않은 풀이다. 제대로 읽었다면 s - t, u - v를 잇는 vertex-disjoint path를 찾는 문제로, maximum flow를 짰고 틀렸다. 데이터탓이라고 정신승리후 끝냄. E : Roommate 옛날에 AC했었다. 풀이는 대충... 이랬던거 같다.dp[i][j][t1][t2] -> 지성(0번)이 i번 task까지 "완벽히" 완료했으며, 영표(1번)가 j번 task까지 "완벽히" 완료했고, t1번째 사람이 i+1 / j+1번째 task를 t2 시간동안 돌렸다.점..
- Total
- Today
- Yesterday