아롱이의 PS하는 블로그

[Python] 백준 3679 - 단순 다각형

https://www.acmicpc.net/problem/3679 문제평면 위의 점의 집합이 주어졌을 때, 다각형을 만드는 프로그램을 작성하시오. 집합의 모든 점은 다각형의 꼭짓점이어야 하고, 집합에 없는 점을 다각형의 꼭짓점으로 가질 수 없다. 다각형의 두 선분은 연속하는 두 선분의 교점을 제외하고는 교차할 수 없다.예를 들어, 왼쪽 그림의 점으로 만든 다각형은 오른쪽과 같다.항상 문제의 조건을 만족하는 다각형만 입력으로 주어지며, 가능한 다각형이 여러 가지인 경우에는 아무거나 출력해도 된다. 두 점이 같은 위치에 있는 경우는 없으며, 모든 점이 한 직선위에 있는 경우는 없다.입력첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트..

[Python] 백준 30645 - 인형 전시

https://www.acmicpc.net/problem/30645문제탁자 위에 인형을 전시하려고 한다. 탁자는 위에서 보았을 때 R개의 행과 C개의 열을 가진 R × C개의 칸을 가진 2차원 배열이며, 각 칸에 하나의 인형을 전시할 수 있다. 현재 전시할 수 있는 인형은 N개이며, 탁자 위에 N개의 인형을 모두 전시할 필요는 없다.탁자를 정면으로 보면 1행에 놓은 인형들이 맨 앞쪽에 있는 방향으로 보게 되는데, 같은 열에 있는 인형들에 대해 앞쪽 행에 인형을 놓은 경우 앞쪽 인형보다 뒤쪽 행에 있고 높이가 앞쪽 인형의 높이 이하인 인형은 앞쪽 인형에 가려져 보이지 않게 된다.이때, 탁자에 인형들을 적당히 배치했을 때 탁자의 정면 방향에서 보이는 인형의 개수의 최댓값을 구하는 프로그램을 작성하시오.입력첫..

[Python] 백준 14247 - 나무 자르기

https://www.acmicpc.net/problem/14247문제영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n$n$일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 나무들이 밤만 되면 매우 빠른 속도로 자라는데, 그 자라는 길이는 나무마다 다르다.따라서, 어느 나무를 먼저 잘라가느냐에 따라서 총 구할 수 있는 나무의 양이 다른데,나무의 처음 길이와 하루에 자라는 양이 주어졌을 때, 영선이가 얻을 수 있는 최대 나무양을 구하시오.참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다.입력첫째 줄에는 나무의 개수 n개가 있다. 나무는 1번부터 n번까지 있다.다음 줄에는 ..

https://www.acmicpc.net/problem/4008문제1부터 n까지 번호가 붙여진 n명의 병사들로 이루어진 군대의 지휘관이 있다. 이 지휘관은 앞으로의 전투를 위하여 n명의 병사들을 여러 개의 특공대로 나누고자 한다. 결속력과 사기를 높이기 위하여 각 특공대는 {i, i+1, ..., i+k}형태의 번호가 연속하는 병사들로 구성된다.각 병사 i의 전투력은 xi이다. 병사들 {i, i+1, ..., i+k}로 구성된 특공대의 전투력 x는 원래는 각 병사의 전투력의 합으로 계산되었다. 달리 말하면 x = xi + xi+1 + ... + xk이었다.그러나 여러 해의 영광스러운 승리를 통하여 특공대의 전투력을 다음과 같이 조정해야 하는 것으로 결론을 내렸다: 특공대의 조정된 전투력 x′는 등식 x..

https://www.acmicpc.net/problem/14751문제There are two distinct horizontal lines hupper and hlower in the xy-coordinate plane and n line segments connecting them. One endpoint of each segment lies on hupper and the other on hlower. All endpoints of the segments are distinct. All segments are numbered from 1 to n. Consider a horizontal line hi located between hupper and hlower, which will be given ..

https://www.acmicpc.net/problem/13263문제높이가 a1, a2, ..., an인 나무 n개를 전기톱을 이용해서 자르려고 한다.i번 나무에 전기톱을 사용할 때 마다 그 나무의 높이는 1만큼 감소한다. 전기톱은 사용할 때 마다 충전해야 한다. 전기톱을 충전하는 비용은 완전히 자른 나무의 번호에 영향을 받는다. 즉, 높이가 0이 되어버린 나무의 번호에 영향을 받는다. 완전히 잘려진 나무의 번호 중 최댓값이 i이면, 전기톱을 충전하는 비용은 bi이다. 완전히 잘려진 나무가 없다면 전기톱은 충전할 수가 없다. 가장 처음에 전기톱은 충전되어져 있다.나무의 높이 ai와 각각의 나무에 대한 충전 비용 bi가 주어졌을 때, 모든 나무를 완전히 자르는데 (높이를 0으로 만드는데) 필요한 충전 비..

https://www.acmicpc.net/problem/9892문제(직접 핵심만 번역해보겠음)2차원 평면 상에 점들이 여러개 주어진다. width w는 이 점들을 모두 감싸는 두 평행한 직선 사이의 최소 거리이다.예를 들면 다음 그림과 같다.당신은 주어진 점들에 대해서 w^2를 계산한 다음 이 수의 정수 부분만 출력하면 된다. 이 문제를 쉽게 풀게 하기 위해 공식을 하나 제공하겠다. 삼각형 ABC가 있어서 A(xa, ya), B(xb, yb), C(xc, yc)라고 할 때 이 삼각형의 높이 h는과 같이 계산될 수 있다. 여기서 문자 시그마의 값은 ABC가 반시계방향이면 1이고 시계방향이면 -1이다. Figure 2를 참고하라.모든 점들이 일직선에 놓여있다면, width는 0이 된다. 입력첫 번째 줄에는..

https://www.acmicpc.net/problem/10254문제n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.입력첫째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000) 그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주..

https://www.acmicpc.net/problem/1708 문제다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.점의 집합이 주어졌을 때, 볼록 껍질을 이루..

https://www.acmicpc.net/problem/11758 문제2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.출력P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다. 풀이CCW 알고리즘은 주어진 세 점의 방향성을 판별하는 매우매우 유명한 알고리즘이다...