Python Learn the basics Quiz 102

Q>

You are given a list of points on a coordinate plane.

(좌표 평면에 포인트 목록이 제공됩니다.)

We need you find the convex hull formed by these points.

(이 점들에 의해 형성된 볼록한 선체를 찾아야합니다.)

The convex hull of a set X of points in the Euclidean plane is the smallest convex set that contains X.

(유 클리 디안 평면에서 점 집합 X의 볼록한 선체는 X를 포함하는 가장 작은 볼록 집합입니다.)

For instance: when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X. If a point lies on edge, it's included.

(예를 들어, X가 평면의 경계 부분 집합 인 경우, 볼록 선체는 X 주위로 펼쳐지는 고무 밴드에 의해 형성된 모양으로 시각화 될 수 있습니다. 한 점이 가장자리에 있으면 포함됩니다.)

The points are presented as a list of coordinates [x, y] in which x and y are integers.

(점은 x와 y가 정수인 좌표 [x, y] 목록으로 표시됩니다.)

The result returns as a sequence of indexes of points in the given list; points lie on the convex hull in clockwise order (see the picture).

(결과는 주어진리스트에서 점의 인덱스의 시퀀스로 반환됩니다. 점들은 시계 방향으로 볼록한 선체에 놓입니다 (그림 참조).)

The sequence starts from the bottom leftmost point.

(시퀀스는 가장 왼쪽 하단부터 시작합니다.)

Remember: You should return a list of indexes--not the points themselves.

(주의 사항 : 포인트 자체가 아니라 인덱스 목록을 반환해야합니다.)

 

Input: A list of coordinates. Each coordinate is a list of two integers.

         (좌표 목록. 각 좌표는 두 개의 정수 목록입니다.)

 

Output: The list of indexes of coordinates from the given list.

           (지정된 리스트로부터의 좌표의 인덱스의 리스트)

 

Example:

checkio([[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]) == [4, 5, 6, 0, 1, 2, 3]
checkio([[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]) == [1, 0, 6, 3, 5, 2]

 

How it is used: Convex hulls have practical applications in pattern recognition, image processing, statistics,

                     (볼록한 선체는 패턴 인식, 이미지 처리, 통계,)

                     GIS and static code analysis by abstract interpretation.

                     (추상적 해석에 의한 GIS 및 정적 코드 분석.)

                     The concept also serves as a tool and a building block for a number of other

                     (이 개념은 또한 여러 다른 도구와 도구로 사용됩니다.)

                     computational-geometric algorithms such as the rotating calipers method for computing the width

                     (너비를 계산하기위한 회전 캘리퍼스와 같은 컴퓨터 기하학적 알고리즘)

                     and diameter of a point set.

                     (및 점 집합의 직경.)

 

Precondition: 
2 < len(coordinates) < 10
all(0 < x < 10 and 0 < x < 10 for x, y in coordinates)

 

A>

# collections : 컨테이너 데이터 타입들이 포함된 모듈
# tuple : 튜플은 기본적으로 값의 시퀀스를 쉼표로 구분하여 저장할 수 있는 불변(immutable) 리스트
# colletions.namedtuple : 튜플을 편리한 컨테이너로 변환(튜플 안의 값들에 접근하기 위해 정수 인덱스 값들을 사용할 필요가 없음)

from collections import namedtuple

Point = namedtuple('Point', 'x y i')

def checkio(data):
    # Wikibooks 참고
    # https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
    def not_right_turn(a, b, c):
        return (b.x - a.x) * (c.y - a.y) > (b.y - a.y) * (c.x - a.x)

    def half(points):
        hull = []
        for point in points:
            while len(hull) > 1 and not_right_turn(hull[-2], hull[-1], point):
                hull.pop()
            hull.append(point)
        return [p.i for p in hull[:-1]]

    # enumerate : 반복문 사용 시 몇 번째 반복문인지 확인(인덱스 번호와 컬렉션의 원소를 tuple형태로 반환)
    points = sorted(Point(x, y, i) for i, (x, y) in enumerate(data))

    return half(points) + half(reversed(points))

if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert checkio(
        [[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]
    ) == [4, 5, 6, 0, 1, 2, 3], "First example"
    assert checkio(
        [[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]
    ) == [1, 0, 6, 3, 5, 2], "Second example"

 

O>

Your result: [4,0,1,3,5]

Pass: checkio([[2,3],[6,3],[3,2],[7,2],[2,1],[6,1]])

 

S>

https://py.checkio.org