結果

問題 No.199 星を描こう
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-04-29 10:29:24
言語 Python2
(2.7.18)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 6,431 bytes
コンパイル時間 60 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-06-09 13:49:44
合計ジャッジ時間 1,510 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
7,168 KB
testcase_01 AC 14 ms
7,168 KB
testcase_02 AC 14 ms
7,168 KB
testcase_03 AC 13 ms
7,040 KB
testcase_04 AC 13 ms
6,944 KB
testcase_05 AC 14 ms
7,168 KB
testcase_06 AC 14 ms
7,168 KB
testcase_07 AC 14 ms
7,168 KB
testcase_08 AC 14 ms
7,040 KB
testcase_09 AC 14 ms
7,040 KB
testcase_10 AC 15 ms
7,168 KB
testcase_11 AC 14 ms
7,040 KB
testcase_12 AC 14 ms
7,040 KB
testcase_13 AC 14 ms
7,168 KB
testcase_14 AC 13 ms
7,168 KB
testcase_15 AC 14 ms
7,168 KB
testcase_16 AC 14 ms
7,040 KB
testcase_17 AC 14 ms
6,940 KB
testcase_18 AC 13 ms
7,040 KB
testcase_19 AC 14 ms
7,168 KB
testcase_20 AC 14 ms
7,040 KB
testcase_21 AC 14 ms
7,040 KB
testcase_22 AC 14 ms
6,940 KB
testcase_23 AC 14 ms
7,168 KB
testcase_24 AC 13 ms
7,168 KB
testcase_25 AC 13 ms
6,944 KB
testcase_26 AC 13 ms
7,040 KB
testcase_27 AC 14 ms
7,168 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/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'
0