[C++] 과제 2: 포로 수용소 - Convex Hull 응용

제출은 .c/.cpp/.java 파일 하나만 제출해주세요.

 

2차원 좌표 (0, 0) 부터 (N, N)로 표현되는 포로 수용소 안에 M명의 포로들이 있다. 포로들은 이 좌표의 정수점 위에 있고, 한 점 위에 두명 이상의 포로가 있는 경우는 없다. 또, 한 직선 위에 세 명 또는 그 이상의 포로가 오는 경우도 없다. 포로들은 이동하지 않는다. 

 

포로를 감시하는 것이 너무 힘들어서, 포로들의 일부에게 다른 포로를 감시하는 권한을 주려고 한다. 가능한 한 가장 적은 수의 포로에게 감시 권한을 주려고 하는데, 한 가지 제약 조건이 있다. 감시 권한이 없는 포로는, 감시 권한이 있는 포로 세 명을 이어서 만들어지는 삼각형 안에 반드시 들어 있어야 한다. 

 

포로 수용소의 크기 N, 포로의 수 M이 주어졌을 때, 감시 권한이 있는 포로와 없는 포로의 수를 출력하는 프로그램을 작성하시오. 

 

입력 

표준 입력으로 입력을 받는다. 첫 줄에는 두 정수 포로 수용소의 크기 N, 포로의 수 M이 주어진다. N은 unsigned int로 표현 가능한 범위 이내인 정수이며, M은 10만 이하이다. 다음 M줄에는 차례대로 포로의 위치를 나타내는 두 정수  X Y가 주어지는데, X, Y는 0 이상 N 이하인 정수이다. 

 

출력 

표준 출력으로 출력한다. 한 줄에 두 정수를 사이에 공백 하나를 두고 출력한다. 첫번째 정수는 감시 권한이 있는 포로의 수이며, 두번째 정수는 감시 권한이 없는 포로의 수이다. 둘의 합은 당연히 M이다. 

 

예제 입력 1

100 6

1 1 

2 3 

1 5

5 5

4 3

5 1

예제 출력 1

4 2

 

예제 입력 2

100 4

3 3 

6 3

1 1 

4 1

예제 출력 2

4 0

 

감점된 코드 - 수정필요

#include <iostream>
#include <stack>
#include <stdlib.h>
#include <cmath>
using namespace std;

struct Point
{
    int x, y;
};

Point p0;

Point nextToTop(stack<Point>& S)
{
    Point p = S.top();
    S.pop();
    Point res = S.top();
    S.push(p);
    return res;
}

void swap(Point& p1, Point& p2)
{
    Point temp = p1;
    p1 = p2;
    p2 = temp;
}

int distSq(Point p1, Point p2)
{
    return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2);
}

int orientation(Point a, Point b, Point c)
{
    int val = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);

    if (val == 0) return 0;  // colinear
    else if (val < 0)
        return 2;    // counterclockwise direction
    return 1;    // clockwise direction
}

int compare(const void* vp1, const void* vp2)
{
    Point* p1 = (Point*)vp1;
    Point* p2 = (Point*)vp2;

    int o = orientation(p0, *p1, *p2);
    if (o == 0)
        return (distSq(p0, *p2) >= distSq(p0, *p1)) ? -1 : 1;

    return (o == 2) ? -1 : 1;
}

int convexHull(Point points[], int n)
{
    int ymin = points[0].y, min = 0;

    for (int i = 1; i < n; i++)
    {
        int y = points[i].y;

        if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
            ymin = points[i].y, min = i;
    }

    swap(points[0], points[min]);

    p0 = points[0];
    qsort(&points[1], n - 1, sizeof(Point), compare);

    int m = 1;
    try {
        for (int i = 1; i < n; i++)
        {
            while (i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0)
                i++;
            points[m] = points[i];
            m++;
        }
        if (m < 3) throw m;
    }
    catch (int expn) {
        cout << "점이 세개 이상이어야 함" << endl;
    }

    stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);

    for (int i = 3; i < m; i++)
    {
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }

    int check = 0;
    while (!S.empty())
    {
        S.pop();
        check++;
    }

    return check;
}

int main()
{
    unsigned int N, X, Y;
    int M;
    int auth, noauth;

    cin >> N >> M;
    Point* points = new Point[M];
    for (int i = 0; i < M; i++) {
        cin >> X >> Y;
        points[i].x = X;
        points[i].y = Y;
    }

    auth = convexHull(points, M);
    noauth = M - auth;
    cout << auth << " " << noauth;

    return 0;
}

 

https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

Convex Hull | Set 2 (Graham Scan) - GeeksforGeeks

점수 5/10