신혜의 직선 긋기 게임

1. 신혜의 직선 긋기 게임 2. 오케이 3. 모든 것이 정리 됨 4. 퀵 소트 하는 이유랑 5. 선분을 모두 한 곳에 저장하고 6. 이것중에 평행한 것을 제거하는 방법에 대해서 익힘

#include <stdio.h> #define MAX 10 void qsort(float * degree, int left, int right) { float pivot = degree[left]; int i = left + 1; int j = right; float tmp; while (1) { while ((degree[i] < pivot) & (i < right)) i++; while ((degree[j] > pivot)) j--; if (i < j) { tmp = degree[i]; degree[i] = degree[j]; degree[j] = tmp; } else break; i++; j--; } degree[left] = degree[j]; degree[j] = pivot; if (j < right) qsort(degree, j + 1, right); if (j > left) qsort(degree, left, j - 1); } int main(void) { freopen("input.txt", "r", stdin); int tc; int tc_idx; scanf("%d", &tc); for (tc_idx = 1; tc_idx <= tc; tc_idx++) { int N; int i, j; int point[MAX + 2][2]; float degree[MAX*MAX]; int count = 0; int tail = 0; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%d %d", &point[i][0], &point[i][1]); // 0에는 x, 1에는 y 좌표가 저장됨 for(i=1; i<=N; i++) for (j = i + 1; j <= N; j++) { if (((point[j][0] - point[i][0]) != 0) & ((point[j][1] - point[i][1]) != 0)) // 동일한 점이 아니면 degree[count++] = (float)(point[j][1] - point[i][1]) / (float)(point[j][0] - point[i][0]); // 디그리 저장함 if (((point[j][0] - point[i][0]) != 0) & ((point[j][1] - point[i][1]) == 0)) // 수직이면 degree[count++] = (float)10000; if (((point[j][0] - point[i][0]) == 0) & ((point[j][1] - point[i][1]) != 0)) // 수평이면 degree[count++] = (float)0; } qsort(degree, 0, count - 1); // 총 6개의 선분을 그을 수 있음, 이것을 정렬하고 바로 옆과 비교만 진행하면 되므로, for (i = 0; i < count - 1; i++) if (degree[i] != degree[i + 1]) // 수평인 것을 제거함 tail++; tail++; printf("#%d %d\n", tc_idx, tail); } return 0; }