https://www.acmicpc.net/problem/17403 17403번: 가장 높고 넓은 성 첫 번째 줄에 n개의 정수 x1, x2, ..., xn을 공백으로 구분하여 출력한다. xi는 i 번째 표지판이 사용되었을 경우 사용된 층수이며, 사용되지 않았으면 0이다. www.acmicpc.net n 개의 표지판을 사용해 각 층별로 가장 넓은 면적을 확보하면서 가장 높이 성을 쌓았을 때, 각 표지판들이 몇 번째 층고에 사용되었는지 구하는 문제다. 1층부터 최대한 넓은 면적을 확보하기 위해 모든 표지판들의 좌표를 이용해 볼록껍질을 구성한다. 볼록 껍질에서 꼭지점을 이루는 점들이 표지판의 위치가 된다. 볼록 껍질 내부에 있거나 꼭지점이 아닌 변 위에 있는 점은 볼록 껍질을 구성하지 못한 점이다. 이러한 ..

네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지 판별하는 문제다. ccw 를 이용해 한 점을 잡아 각도가 작은 순으로 정렬 후 정사각형임을 판별할 수도 있지만, 판별하는 대상이 정사각형이기 때문에, 단순정렬만 이용해도 풀이가 가능하다. 2차원 평면 상에서 정사각형은 다음과 같이 나타낼 수 있다. 정사각형을 판별하기 위해 두 가지 조건을 만족하는지 확인한다. - 네 변의 길이가 같다 - 두 대각선의 길이가 같다. 따라서 한 점을 기준으로 나머지 점들의 좌표를 시계 또는 반시계 방향으로 정렬한 뒤, 네 변의 길이와 두 대각선의 길이가 같은지 판별한다. 입력으로 받은 점들을 배열에 넣고, 점들을 x 좌표, y 좌표 순으로 정렬하고, 맨 처음 점을 기준점 p 로 놓는다. x 좌표가 가장..