結果
| 問題 |
No.199 星を描こう
|
| ユーザー |
 yuppe19 😺
|
| 提出日時 | 2015-04-29 10:29:24 |
| 言語 | Python2 (2.7.18) |
| 結果 |
AC
|
| 実行時間 | 16 ms / 2,000 ms |
| コード長 | 6,431 bytes |
| コンパイル時間 | 215 ms |
| コンパイル使用メモリ | 7,040 KB |
| 実行使用メモリ | 7,168 KB |
| 最終ジャッジ日時 | 2024-12-30 03:33:00 |
| 合計ジャッジ時間 | 1,676 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#!/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'