#23437 (Python2) No.199 星を描こう

提出ソース

結果

問題	No.199 星を描こう
ユーザー	yuppe19 😺
提出日時	2015-04-29 10:29:24
言語	Python2 (2.7.18)
結果	AC
実行時間	14 ms / 2,000 ms
コード長	6,431 bytes
コンパイル時間	43 ms
コンパイル使用メモリ	6,956 KB
実行使用メモリ	7,064 KB
最終ジャッジ日時	2023-08-28 18:38:16
合計ジャッジ時間	1,412 ms
ジャッジサーバーID （参考情報）	judge13 / judge12

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 7,036 KB
testcase_01	AC	14 ms 6,964 KB
testcase_02	AC	13 ms 7,024 KB
testcase_03	AC	14 ms 6,988 KB
testcase_04	AC	13 ms 6,852 KB
testcase_05	AC	12 ms 7,020 KB
testcase_06	AC	13 ms 6,928 KB
testcase_07	AC	13 ms 6,924 KB
testcase_08	AC	12 ms 6,860 KB
testcase_09	AC	12 ms 7,024 KB
testcase_10	AC	13 ms 6,924 KB
testcase_11	AC	13 ms 6,872 KB
testcase_12	AC	13 ms 7,056 KB
testcase_13	AC	12 ms 7,000 KB
testcase_14	AC	13 ms 7,024 KB
testcase_15	AC	13 ms 7,000 KB
testcase_16	AC	12 ms 6,868 KB
testcase_17	AC	13 ms 6,856 KB
testcase_18	AC	13 ms 7,032 KB
testcase_19	AC	12 ms 6,860 KB
testcase_20	AC	13 ms 6,856 KB
testcase_21	AC	12 ms 6,940 KB
testcase_22	AC	12 ms 6,944 KB
testcase_23	AC	13 ms 6,860 KB
testcase_24	AC	13 ms 7,064 KB
testcase_25	AC	12 ms 6,924 KB
testcase_26	AC	12 ms 7,020 KB
testcase_27	AC	12 ms 6,848 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#!/usr/bin/python
# -*- coding: utf-8 -*-
# †
from collections import namedtuple
from itertools import izip
from operator import itemgetter
Point = namedtuple('Point', 'x, y, z')

## (ΦωΦ)＜外積 http://oshiete.goo.ne.jp/qa/2435435.html
#def cross_product(o, a, b):
#    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
## (ΦωΦ)＜凸包
#def convex_hull(points):
#    points = sorted(set(points))
#    if len(points) <= 1:
#        return points
#    def _alg(points):
#        res = []
#        for p in points:
#            while len(res) > 1 and cross_product(res[-2], res[-1], p) <= 0:
#                res.pop()
#            res.append(p)
#        return res
#    def build(points):
#        lower = _alg(points)
#        upper = _alg(points[::-1])
#        return lower, upper
#    lower, upper = build(points)
#    return lower[:-1] + upper[:-1]

def vecNormal(vec1, vec2, vec3):
    """Returns a vector that is orthogonal on C{triangle}."""
    return vecCrossProduct(vecSub(vec2, vec1), vecSub(vec3, vec1))

def vecDistanceAxis(axis, vec):
    """Return distance between the axis spanned by axis[0] and axis[1] and the
    vector v, in 3 dimensions. Raises ZeroDivisionError if the axis points
    coincide.
    """
    return vecNorm(vecNormal(axis[0], axis[1], vec)) / vecDistance(*axis)

def vecDistanceTriangle(triangle, vert):
    """Return (signed) distance between the plane spanned by triangle[0],
    triangle[1], and triange[2], and the vector v, in 3 dimensions.
    """
    normal = vecNormal(*triangle)
    return vecDotProduct(normal, vecSub(vert, triangle[0])) / vecNorm(normal)

def vecCrossProduct(vec1, vec2):
    """The vector cross product (in 3d). """
    return (vec1.y * vec2.z - vec1.z * vec2.y,
            vec1.z * vec2.x - vec1.x * vec2.z,
            vec1.x * vec2.y - vec1.y * vec2.x)

def vecSub(vec1, vec2):
    """Vector substraction."""
    return Point(*(a - b for a, b in izip(vec1, vec2)))

def vecAdd(vec1, vec2):
    return Point(*(a + b for a, b in izip(vec1, vec2)))

def vecDotProduct(vec1, vec2):
    """The vector dot product (any dimension)."""
    return sum(x1*x2 for x1, x2 in izip(vec1, vec2))

def vecNorm(vec):
    """Norm of a vector (any dimension)."""
    return vecDotProduct(vec, vec) ** .5

def vecDistance(vec1, vec2):
    """Return distance between two vectors (any dimension)."""
    return vecNorm(vecSub(vec1, vec2))

def basesimplex3d(vertices, precision=0.0001):
    """Find four extreme points, to be used as a starting base for the
    quick hull algorithm L{qhull3d}.

    The algorithm tries to find four points that are
    as far apart as possible, because that speeds up the quick hull
    algorithm. The vertices are ordered so their signed volume is positive.

    If the volume zero up to C{precision} then only three vertices are
    returned. If the vertices are colinear up to C{precision} then only two
    vertices are returned. Finally, if the vertices are equal up to C{precision}
    then just one vertex is returned.

    :param vertices: The vertices to construct extreme points from.
    :param precision: Distance used to decide whether points coincide,
        are colinear, or coplanar.
    :return: A list of one, two, three, or four vertices, depending on the
        the configuration of the vertices.
    """
    extents = sorted(range(3), key=lambda i:
                               max(vert[i] for vert in vertices)
                             - min(vert[i] for vert in vertices))
    vert0 = min(vertices, key=itemgetter(*extents))
    vert1 = max(vertices, key=itemgetter(*extents))
    if vecDistance(vert0, vert1) < precision:
        return [vert0]
    vert2 = max(vertices, key=lambda vert:
                          vecDistanceAxis((vert0, vert1), vert))
    if vecDistanceAxis((vert0, vert1), vert2) < precision:
        return [vert0, vert1]
    vert3 = max(vertices, key=lambda vert:
                          abs(vecDistanceTriangle((vert0, vert1, vert2), vert)))
    orientation = vecDistanceTriangle((vert0, vert1, vert2), vert3)
    if orientation > precision:
        return [vert0, vert1, vert2, vert3]
    elif orientation < -precision:
        return [vert1, vert0, vert2, vert3]
    else:
        return [vert0, vert1, vert2]

# adapted from
# http://en.literateprograms.org/Quickhull_(Python,_arrays)
def qdome2d(vertices, base, normal, precision=0.0001):
    """Build a convex dome from C{vertices} on top of the two C{base} vertices,
    in the plane with normal C{normal}. This is a helper function for
    L{qhull2d}, and should usually not be called directly.

    :param vertices: The vertices to construct the dome from.
    :param base: Two vertices that serve as a base for the dome.
    :param normal: Orientation of the projection plane used for calculating
        distances.
    :param precision: Distance used to decide whether points lie outside of
        the hull or not.
    :return: A list of vertices that make up a fan of the dome."""
    vert0, vert1 = base
    outer = [(dist, vert) 
             for dist, vert
             in izip((vecDotProduct(vecCrossProduct(normal,
                                                    vecSub(vert1, vert0)),
                                    vecSub(vert, vert0))
                      for vert in vertices),
                     vertices)
             if dist > precision]
    if outer:
        pivot = max(outer, key=lambda i: i[0])[1]
        outer_verts = map(itemgetter(1), outer)
        return qdome2d(outer_verts, [vert0, pivot], normal, precision) \
             + qdome2d(outer_verts, [pivot, vert1], normal, precision)[1:]
    else:
        return base

def qhull2d(vertices, normal, precision=0.0001):
    """Simple implementation of the 2d quickhull algorithm in 3 dimensions for
    vertices viewed from the direction of C{normal}.
    Returns a fan of vertices that make up the surface. Called by
    L{qhull3d} to convexify coplanar vertices."""
    base = basesimplex3d(vertices, precision)
    if len(base) >= 2:
        vert0, vert1 = base[:2]
        return qdome2d(vertices, [vert0, vert1], normal, precision) \
             + qdome2d(vertices, [vert1, vert0], normal, precision)[1:-1]
    else:
        return base

xys = []
for _ in xrange(5):
    x, y = map(float, raw_input().split())
    xys.append(Point(x, y, 0))

if len(qhull2d(xys, Point(0,0,100))) == 5:
    print 'YES'
else:
    print 'NO'

yukicoder

結果

テストケース

ソースコード