BAEKJOON 2700 - Interior Points of Lattice Polygons

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

문제

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

The lattice points on the boundary of the polygon are boundary points (open dots in the figure above) and the points inside and not on the polygon are interior points (filled in dots in the figure above). 

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. Note that any line between two points inside (and not on the boundary of) the polygon is entirely inside (and not on the boundary of) the polygon.

The interior points of a convex lattice polygon on any horizontal line form a single segment from a leftmost point to a rightmost point (which may be the same). Note that there may be no interior points (A), or only one (B), or isolated points (C) as shown in the figures below. 

Write a program that reads the vertices of a convex lattice polygon in standard order and outputs the interior points as a list of horizontal line segments. The vertices of a lattice polygon are in standard order if: 

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. 
Vertices are given in clockwise order around the polygon.

입력

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 vertices N, (3 ≤ N ≤ 50), of the polygon. The remaining lines in the data set contain the vertices, one per line in standard order. Each line contains the decimal integer x coordinate, a space and the decimal integer y coordinate.

출력

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 number of horizontal lines which contain interior points (this may be zero (0) or more). The lines of interior points, if any, follow, one per line in order of decreasing y value. Each line contains the decimal integer y coordinate, a single space and the decimal integer x coordinate of the left most point, a single space and the decimal integer x coordinate of the right most point.

예제 입력 

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

예제 출력 

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

힌트

출처

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

앞에서 풀었던 Convex Hull 문제와 비슷하면서도 다른 점이 많았던 문제였습니다.

해당 문제를 풀기위해 우선 경계점을 모두 구해 경계점은 피해갈 수 있도록 했습니다.

이후 가능한 모든 점을 탐색하며 외적을 이용한 ccw 알고리즘을 통해 내부에 있는 모든 점을 찾는 방법으로 풀어봤습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
#include <vector>
using namespace std;
 
struct Point
{
    int x, y;
};
 
struct Answer
{
    int y, x1, x2;
    Answer(int _y, int _x1, int _x2) : y(_y), x1(_x1), x2(_x2) {}
};
 
Point p0;
 
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;  
    return (val > 0) ? 1 : 2; 
}
 
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 x, int y, int& selectedIndex)
{
    p0 = points[0];
    qsort(&points[1], n - 1, sizeof(Point), compare);
 
    for (int i = 1; i < n; i++)
    {
        if (points[i].x == x && points[i].y == y)
        {
            selectedIndex = i;
            int nextIndex = i + 1;
            if (nextIndex == n)
                nextIndex = 0;
            return orientation(points[i - 1], points[i], points[nextIndex]);
        }
    }
}
 
bool isBoundaryPoints(vector<Point>& boundaryPoints, int y, int x)
{
    for (auto& elem : boundaryPoints)
    {
        if (elem.x == x && elem.y == y)
            return true;
    }
    return false;
}
 
void calcBoundaryPoints(vector<Point>& boundaryPoints, Point* points, int n)
{
    for (int i = 0; i < n; i++)
    {
        int nextIndex = i + 1;
        if (i == n - 1)
            nextIndex = 0;
 
        int diffX = points[i].x - points[nextIndex].x;
        int diffY = points[i].y - points[nextIndex].y;
        if (diffX == 0 || diffY == 0 || max(abs(diffX), abs(diffY)) % min(abs(diffX), abs(diffY)) == 0)
        {
            if (diffX == 0)
            {
                diffY /= abs(diffY);
            }
            else if (diffY == 0)
            {
                diffX /= abs(diffX);
            }
            else
            {
                int slope = min(abs(diffX), abs(diffY));
                diffX /= slope;
                diffY /= slope;
            }
 
            int count = 1;
            while (true)
            {
                Point newPoint;
                newPoint.x = points[i].x - diffX * count;
                newPoint.y = points[i].y - diffY * count;
                if (points[nextIndex].x == newPoint.x && points[nextIndex].y == newPoint.y)
                    break;
                boundaryPoints.push_back(newPoint);
                count++;
            }
        }
    }
}
 
int main()
{        
    int cases, n, k;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        int n;
        cin >> n;
        Point* points = new Point[n + 1];
        vector<Point> boundaryPoints;
        vector<Answer> ret;
        int minY = INT_MAX;
        int minX = INT_MAX;
        int maxX = INT_MIN;
        for (int i = 0; i < n; i++)
        {
            cin >> points[i].x >> points[i].y;
            boundaryPoints.push_back(points[i]);
            minY = min(minY, points[i].y);
            minX = min(minX, points[i].x);
            maxX = max(maxX, points[i].x);
        }
        calcBoundaryPoints(boundaryPoints, points, n);
        int selectedIndex = n;
        for (int y = points[0].y - 1; y > minY; y--)
        {
            for (int x = minX + 1; x < maxX; x++)
            {
                if (isBoundaryPoints(boundaryPoints, y, x))
                    continue;
                points[selectedIndex].x = x;
                points[selectedIndex].y = y;
                int ori = convexHull(points, n + 1, x, y, selectedIndex);
                if (ori == 1)
                {
                    int x2 = x + 1;
                    for (; x2 < maxX; x2++)
                    {
                        if (isBoundaryPoints(boundaryPoints, y, x2))
                            break;
                        points[selectedIndex].x = x2;
                        points[selectedIndex].y = y;
                        ori = convexHull(points, n + 1, x2, y, selectedIndex);
                        if (ori != 1)
                            break;
                    }
 
                    Answer answer(y, x, x2 - 1);
                    ret.push_back(answer);
                    
                    break;
                }
            }
        }
        cout << ret.size() << endl;
        for (auto& ans : ret)
        {
            cout << ans.y << " " << ans.x1 << " " << ans.x2 << endl;
        }
        delete[] points;
    }
 
    return 0;
}