BAEKJOON 2699 - Convex Hull of Lattice Points

문제: https://www.acmicpc.net/problem/2699

문제

A lattice point is a point with integer coordinates. A lattice polygon is a polygon with all vertices lattice points. 

A polygon is convex if any line segment between two points of the polygon is inside (or on the boundary of) the polygon. Equivalently, the interior angle at each polygon vertex is less than 180 degrees. 

For a set S, of lattice points, the convex hull is the smallest convex (lattice) polygon which contains all points of the set. (The vertices of the convex hull must be members of the set of lattice points). If all the points are on a single straight line, the convex hull will be a line segment (a degeneratepolygon – see rightmost diagram below). In the diagrams below, the points of the set are indicated by solid dots, the vertices of the convex hull by X’s and the convex hull is drawn connecting the vertices. 

Note that not all points on the convex hull polygon are vertices.

The vertices of a lattice polygon are in standard order if: 

1. The first vertex is the one with the largest y value. If two vertices have the same y value, the one with the smaller x value is the first. 
2. Vertices are given in clockwise order around the polygon. 

Write a program that reads a set of lattice points and outputs the vertices of the convex hull of the points in standard order. 

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer giving the number of points N, (3 ≤ N ≤ 50), in the set. The remaining lines in the data set contain the points in the set, at most 5 points per line (the last line may have fewer). Each point consists of 2 space separated decimal integer values representing the x and y coordinates respectively. 

출력

For each data set there are multiple lines of output. The first line contains a decimal integer giving the data set number followed by a single space, followed by a decimal integer giving the total number of vertices of the convex hull. The vertices of the convex hull follow, one per line in standard order. Each line contains the decimal integer x coordinate, a single space and the decimal integer y coordinate. 

예제 입력 

4
25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3
3 1 2 2 1 3
6
1 3 19 1 4 2 2 1 11 2
10 1

예제 출력 

10
4 9
7 9
10 6
10 3
9 2
7 1
2 1
1 2
1 5
2 7
8
3 9
6 9
12 7
12 4
10 -2
7 -2
1 0
1 3
2
1 3
3 1
4
1 3
11 2
19 1
2 1

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2009 Greater New York Programming Contest G번

• 문제를 번역한 사람: baekjoon hahaha
• 잘못된 데이터를 찾은 사람: superwisdom

Convex Hull 을 찾는 Graham's scan 라는 알고리즘을 통해 풀 수 있는 문제입니다.

인터넷에 돌아다니는 해당 알고리즘 코드를 이용하여 공부하며 풀어봤습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <stack>
using namespace std;
 
struct Point
{
    int x, y;
};
 
Point p0;
 
// A utility function to find next to top in a stack
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 (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
 
// 0: p, q and r are colinear
// 1: Clockwise
// 2: Counterclockwise
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
        (q.x - p.x) * (r.y - q.y);
 
    if (val == 0) 
        return 0;  // colinear
    return (val > 0) ? 1 : 2; // clock or counterclock wise
}
 
// A function used by library function qsort() to sort an array of
// points with respect to the first point
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;
}
 
void convexHull(Point points[], int n)
{
    int yMax = points[0].y;
    int maxIndex = 0;
    for (int i = 1; i < n; i++)
    {
        int y = points[i].y;
 
        // Pick the bottom-most or chose the left
        // most point in case of tie
        if ((y > yMax) || (yMax == y && points[i].x < points[maxIndex].x))
            yMax = points[i].y, maxIndex = i;
    }
 
    // Place the bottom-most point at first position
    swap(points[0], points[maxIndex]);
 
    // Sort n-1 points with respect to the first point.
    // A point p1 comes before p2 in sorted ouput if p2
    // has larger polar angle (in counterclockwise
    // direction) than p1
    p0 = points[0];
    qsort(&points[1], n - 1, sizeof(Point), compare);
 
    // If two or more points make same angle with p0,
    // Remove all but the one that is farthest from p0
    // Remember that, in above sorting, our criteria was
    // to keep the farthest point at the end when more than
    // one points have same angle.
    int m = 1; // Initialize size of modified array
    for (int i = 1; i<n; i++)
    {
        // Keep removing i while angle of i and i+1 is same
        // with respect to p0
        while (i < n - 1 && orientation(p0, points[i], points[i + 1]) == 0)
            i++;
 
        points[m] = points[i];
        m++;  // Update size of modified array
    }
 
    // If modified array of points has less than 3 points,
    // convex hull is not possible
    if (m < 3)
    {
        cout << m << endl;
        for (int i = 0; i < m; i++)
        {
            cout << points[i].x << " " << points[i].y << endl;
        }
        return;
    }
 
    // Create an empty stack and push first three points
    // to it.
    stack<Point> S;
    S.push(points[0]);
    S.push(points[1]);
    S.push(points[2]);
 
    // Process remaining n-3 points
    for (int i = 3; i < m; i++)
    {
        // Keep removing top while the angle formed by
        // points next-to-top, top, and points[i] makes
        // a non-left turn
        while (orientation(nextToTop(S), S.top(), points[i]) != 2)
            S.pop();
        S.push(points[i]);
    }
 
    cout << S.size() << endl;
    cout << p0.x << " " << p0.y << endl;
    // Now stack has the output points, print contents of stack
    while (S.size() > 1)
    {
        Point p = S.top();
        cout << p.x << " " << p.y << endl;
        S.pop();
    }
 
}
 
int main()
{
    int cases;
    cin >> cases;
    for (int i = 0; i < cases; i++)
    {
        int n;
        cin >> n;
        Point* points = new Point[n];
        for (int i = 0; i < n; i++)
        {
            cin >> points[i].x >> points[i].y;
        }
        convexHull(points, n);
        delete[] points;
    }
 
    return 0;
}