My life story

1. 문제 링크 https://www.acmicpc.net/problem/10254 10254번: 고속도로 문제 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 �� www.acmicpc.net 2. 문제 개요 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 도시의 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾는 프로그램을 작성하시오. 3. 문제 힌트 그냥 Brute Force로 푼다면 이문제는 O(n^2) 시간 내에 풀 수 있다. 하지만 N이 20만이다. 그래서 O(nlo..

1. 문제 링크 https://www.acmicpc.net/problem/13263 13263번: 나무 자르기 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄에는 a1, a2, ..., an이, 셋째 줄에는 b1, b2, ..., bn이 주어진다. (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) a1 = 1이고, bn = 0이며, a1 b2 > ... > bn을 만족�� www.acmicpc.net 2. 문제 개요 높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다. i번 나무에 전기톱을 사용할 때마다, 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자..

1. 문제 링크 https://www.acmicpc.net/problem/2699 2699번: 격자점 컨벡스헐 문제 정수좌표를 갖는 점을 격자점이라고 한다. 격자 다각형은 모든 꼭짓점이 격자점으로 이루어진 다각형이다. 만약, 다각형의 두 꼭짓점을 잇는 모든 선분이 다각형 내부(또는 경계)에 있다면 www.acmicpc.net 2. 문제 개요 좌표가 주어지고 컨벡스 헐을 이루는 점의 개수, 좌표(x, y) 순서를 조건에 맞는 순서대로 출력할 것. 조건은 1. 첫 번째 곡짓점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫 번째 점이다. 2. 그 다음 점부터는 시계방향 순서이다. 3. 문제 힌트 평소에 알고 있는 컨벡스 헐 알고리즘인 그라함 스캔 알고리즘은 y좌표가 가장 작고 ..

1. 문제 링크 https://www.acmicpc.net/problem/2254 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려고 한다. 감옥은 하나의 점으로 표현된다. 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야하고, 담 안에 포함되는 담이 있다면 완전히 ..

1. 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x�� www.acmicpc.net 2. 문제 개요 볼록 껍질(Convex hull)을 만드는 최소 점의 개수를 출력하는 프로그램을 작성하시오 3. 문제 힌트 알고리즘을 알고 있어야 한다. 간단히 설명하면, 0번점을 시작으로 2번점이 0->1을 이은 벡터의 시계 반대방향에 있는지, 시계방향에 있는지 구분하는 부분을 작성해야 한다. 다른 블로그에 알고리즘에 대한 설명이 잘 나와있으니까 코드는 아니..