집합과정 Convex

2차원 좌표게에 있는 앤개의 점이 주어짐 앤개의 점으로 구성할 수 있는 Convex Hull 을 이루는 점의 개수를 구하여라  전체 테스트케이스 개수 첫번째 TC의 점 개수 N 첫번째 점의 좌표 x, y 두번째 점의 좌표 x, y

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> typedef long long int int64; typedef struct { int64 x, y; } POINT; POINT PT[100001], HULL[100001]; int prev[100001], next[100001]; #define Swap(a, b) { POINT t = a; a = b; b = t; } void QSort(POINT *P, int l, int r) { int i = l, j = r; int64 p = P[(l + r) / 2].x; while (i <= j) { while (P[i].x < p) ++i; while (P[j].x > p) --j; if (i <= j) { if (P[i].x != P[j].x) Swap(P[i], P[j]) else { if (P[i].y > P[j].y) Swap(P[i], P[j]) } ++i, --j; } } if (l < j) QSort(P, l, j); if (i < r) QSort(P, i, r); } //POINT minus(POINT p, POINT q) { // POINT r; // r.x = p.x - q.x; // r.y = p.y - q.y; // return r; //} //int ccw(POINT p, POINT q) { // return p.x*q.y - p.y*q.x; //} //int ccw3(POINT r, POINT p, POINT q) { // return ccw(minus(p, r), minus(q, r)); //} //int leftTurn(POINT *P, int a, int b, int c) { // return ccw3(P[a], P[b], P[c]) > 0; //} //int rightTurn(POINT *P, int a, int b, int c) { // return ccw3(P[a], P[b], P[c]) < 0; //} //int ConvexHull(POINT *P, int n) { // int i, count = n; // for (i = 0; i < n; ++i) prev[i] = next[i] = 0; // prev[0] = next[0] = 1; //// prev[1] = next[1] = 0; // for (i = 2; i < n; ++i) { // if (P[i].y > P[i - 1].y) prev[i] = i - 1, next[i] = next[i - 1]; // else next[i] = i - 1, prev[i] = prev[i - 1]; // next[prev[i]] = prev[next[i]] = i; // while (leftTurn(P, i, prev[i], prev[prev[i]])) // next[prev[prev[i]]] = i, prev[i] = prev[prev[i]], --count; // while (rightTurn(P, i, next[i], next[next[i]])) // prev[next[next[i]]] = i, next[i] = next[next[i]], --count; // } // return count; //} int64 ccw(POINT p1, POINT p2, POINT p3) { return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x); } int ConvexHull(POINT* P, int n) { int i, t, k = 0; for (i = 0; i < n; ++i) { while (k >= 2 && ccw(HULL[k - 2], HULL[k - 1], P[i]) <= 0) --k; HULL[k++] = P[i]; } for (i = n - 2, t = k + 1; i >= 0; --i) { while (k >= t && ccw(HULL[k - 2], HULL[k - 1], P[i]) <= 0) --k; HULL[k++] = P[i]; } return k - 1; } int main() { freopen("test.txt", "r", stdin); int T, t, N, i; scanf("%d", &T); for (t = 1; t <= T; ++t) { scanf("%d", &N); for (i = 0; i < N; ++i) scanf("%lld %lld", &PT[i].x, &PT[i].y); QSort(PT, 0, N - 1); printf("#%d %d\n", t, ConvexHull(PT, N)); } return 0; }

- 정렬을 하고 - 그것에 대해서 풀이하는 방식이 존재하는 것 같음 - ccw 라는 것이 있나? - 이 풀이를 어떻게 찾아봐야하지?