PS 이야기

문제 링크 K. Trash Removal 다각형이 주어질 때, 다각형이 쓰레기 장으로 들어가기 위한 통로의 최소 너비를 구하는 문제다. 임의의 두 점을 잡아 직선을 그렸을 때, 그 직선이 수직하게 들어간다고 가정하고 너비를 계산한다. 계산된 너비 중 최소 너비가 답이 된다. 이와 같은 알고리즘이 가능한 이유는 다각형을 덮는 볼록 껍데기를 생각했을 때 너비가 최소가 되는 경우는 볼록 껍데기의 변들 중 한 변이 통로의 변과 평행하기 때문이다. #include #include #include using namespace std; int N; int X[101], Y[101]; double w[101][101]; double dist(int a, int b, int c) { double area2 = X[a]*..

문제 링크 A. Cluster Analysis $N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다. $N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다. #include #include int T, N, K; int A[101], par[101]; int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;..

코드포스 GYM 링크 A. Avoiding the Apocalypse 내가 아직 풀지 않았다. B. Button Bashing $n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다. #include #include using namespace std; int T, N, K; int D[3601], A[17]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &K); for (i=1;i1, a&1?".5":""); continue; } int ans = 0; for (i=1;i scnt) q -= scnt; for ..