QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#638921 | #9227. Henry the Plumber | ucup-team3646 | WA | 23ms | 12136kb | Python3 | 9.3kb | 2024-10-13 17:20:17 | 2024-10-13 17:20:17 |
Judging History
answer
# 幾何ライブラリ
from functools import cmp_to_key
from typing import List
from math import*
Point=complex
def point(a,b)->Point:
return a+b*1j
def print_Point(p:Point):
x,y=p.real,p.imag
print('{:.10f}'.format(x),'{:.10f}'.format(y))
def print_float(x:float):
print('{:.10f}'.format(x))
def str_float(x:float)->str:
return '{:.10f}'.format(x)
def norm(p:Point):
return p.real**2+p.imag**2
def cmp(a:Point,b:Point)->bool:
if not equal(a.real,b.real):
if a.real<b.real:return -1
else:return 1
else:
if a.imag<b.imag:return -1
else:return 1
eps=1e-6
# 同じか判定
def equal(a:Point,b:Point)->float:
return abs(a-b)<eps
# 単位ベクトルを求める
def unitVector(a:Point)->Point:
return a/abs(a)
# 内積(dot product):a・b=|a||b|cosΘ
def dot(a:Point,b:Point)->float:
return a.real*b.real+a.imag*b.imag
# 外積(cross product):a×b=|a||b|sinΘ
def cross(a:Point,b:Point)->float:
return a.real*b.imag-a.imag*b.real
# 点pを反時計回りにtheta度回転
def rotate(p:Point,theta:float)->Point:
return (cos(theta)*p.real-sin(theta)*p.imag)+(sin(theta)*p.real+cos(theta)*p.imag)*1j
class Line:
def __init__(self,a,b,c=False):
if c==False:
# a,b は複素数
self.a=a
self.b=b
else:
# ax+by=c
# a,b,c は実数
if equal(a,0):
self.a=(c/b)*1j
self.b=1+(c/b)*1j
elif equal(b,0):
self.a=(c/a)+0j
self.b=(c/a)+1j
else:
self.a=(c/b)*1j
self.b=(c/a)+0j
class Segment:
def __init__(self,a:Point,b:Point):
self.a=a
self.b=b
class Circle:
def __init__(self,p:Point,r:float):
self.p=p
self.r=r
# 射影(projection)
# 直線Lに点pから引いた垂線の足を求める
def projection(L:Line,p:Point)->Point:
t=dot(p-L.a,L.a-L.b)/norm(L.a-L.b)
return L.a+(L.a-L.b)*t
# 反射(reflection)
# 直線Lを対称軸として点pと線対称の位置にある点を求める
def reflection(L:Line,p:Point)->Point:
return p+(projection(L,p)-p)*2
# 点の回転方向
def CounterClockWise(a:Point,b:Point,c:Point)->int:
p=b-a
q=c-a
# a,b,c が反時計回り -> 1
# a,b,c が時計回り -> -1
# c,a,b がこの順で同一直線状 -> 2
# a,b,c がこの順で同一直線状 -> -2
# b,c,a がこの順で同一直線状 -> 0
if cross(p,q)>eps:
return 1
if cross(p,q)<-eps:
return -1
if dot(p,q)<0:
return 2
if norm(p)<norm(q):
return -2
return 0
# 2 直線の直交判定
def isOrthiogonal(a:Line,b:Line)->bool:
return equal(dot(a.b-a.a,b.b-b.a),0)
# 2 直線の平行判定
def isParallel(a:Line,b:Line)->bool:
return equal(cross(a.b-a.a,b.b-b.a),0)
# 2 線分の交差判定
def isIntersect(s:Segment,t:Segment)->bool:
return CounterClockWise(s.a,s.b,t.a)*CounterClockWise(s.a,s.b,t.b)<=0 and CounterClockWise(t.a,t.b,s.a)*CounterClockWise(t.a,t.b,s.b)<=0
# 2 直線の交点
def crossPoint(s:Line,t:Line)->Point:
d1=cross(s.b-s.a,t.b-t.a)
d2=cross(s.b-s.a,s.b-t.a)
if equal(abs(d1),0) and equal(abs(d2),0):
return t.a
return t.a+(t.b-t.a)*(d2/d1)
def distanceBetweenLineAndPoint(l:Segment,p:Point)->float:
return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a)
# 線分lと点pの距離
def distanceBetweenSegmentAndPoint(l:Segment,p:Point)->float:
if dot(l.b-l.a,p-l.a)<eps:
return abs(p-l.a)
if dot(l.a-l.b,p-l.b)<eps:
return abs(p-l.b)
return abs(cross(l.b-l.a,p-l.a))/abs(l.b-l.a)
# 線分s,tの距離
def distanceBetweenSegments(s:Segment,t:Segment)->float:
if(isIntersect(s,t)):
return 0
ans=distanceBetweenSegmentAndPoint(s,t.a)
ans=min(ans,distanceBetweenSegmentAndPoint(s,t.b))
ans=min(ans,distanceBetweenSegmentAndPoint(t,s.a))
ans=min(ans,distanceBetweenSegmentAndPoint(t,s.b))
return ans
# 多角形の面積
def PolygonArea(p:List[Point])->float:
res=0
n=len(p)
for i in range(n):
res+=cross(p[i],p[(i+1)%n])
return res/2
# 凸判定
def isConvex(p:List[Point])->float:
# p は反時計回り
n=len(p)
for i in range(n):
if CounterClockWise(p[(i-1)%n],p[i],p[(i+1)%n])==-1:
return False
return True
# 多角形 g に点 p が含まれるか
def isContained(g:List[Point],p:Point)->int:
# 含む:2,辺上:1,含まない:0
IN=False
n=len(g)
for i in range(n):
a=g[i]-p
b=g[(i+1)%n]-p
if a.imag>b.imag:
a,b=b,a
if a.imag<=0 and 0<b.imag and cross(a,b)<0:
IN^=1
if cross(a,b)==0 and dot(a,b)<=0:
return 1
if IN:
return 2
return 0
# 凸包
def ConvexHull(g:List[Point])->List[Point]:
g.sort(key=cmp_to_key(cmp))
CH=[]
n=len(g)
for p in g:
# 同一直線上の3点を含める -> (<-eps)
# 含めない -> (<eps)
while len(CH)>1 and cross(CH[-1]-CH[-2],p-CH[-1])<-eps:
CH.pop()
CH.append(p)
t=len(CH)
for i in range(n-2,-1,-1):
p=g[i]
while len(CH)>t and cross(CH[-1]-CH[-2],p-CH[-1])<-eps:
CH.pop()
CH.append(p)
return CH[:-1]
# 凸多角形の直径
def ConvexDiameter(p:List[Point])->float:
n=len(p)
i0,j0=0,0
for i in range(1,n):
if p[i].imag>p[i0].imag:
i0=i
if p[i].imag<p[j0].imag:
j0=i
mx=abs(p[i0]-p[j0])
i=i0
j=j0
while i!=j0 or j!=i0:
if(cross(p[(i+1)%n]-p[i],p[(j+1)%n]-p[j])>=0):
j=(j+1)%n
else:
i=(i+1)%n
if abs(p[i]-p[j])>mx:
mx=abs(p[i]-p[j])
return mx
# 凸多角形の切断
# 直線 L.a-L.b で切断して,その左側の凸多角形を返す
def ConvexCut(P:List[Point],L:Line)->List[Point]:
ret=[]
n=len(P)
for i in range(n):
now,nxt=P[i],P[(i+1)%n]
if CounterClockWise(L.a,L.b,now)!=-1:
ret.append(now)
if CounterClockWise(L.a,L.b,now)*CounterClockWise(L.a,L.b,nxt)<0:
ret.append(crossPoint(Line(now,nxt),L))
return ret
# 円の交差判定
def IsIntersectCircle(c1:Circle,c2:Circle)->int:
d=abs(c1.p-c2.p)
# 2 円が離れている
if d>c1.r+c2.r+eps:
return 4
# 外接
if equal(d,c1.r+c2.r):
return 3
# 内接
if equal(d,abs(c1.r-c2.r)):
return 1
# 内包
if d<abs(c1.r-c2.r)-eps:
return 0
# 2 交点を持つ
return 2
# 三角形の内心
def InscribedCircle(a:Point,b:Point,c:Point)->Circle:
A,B,C=abs(b-c),abs(c-a),abs(b-a)
p=point(A*a.real+B*b.real+C*c.real,A*a.imag+B*b.imag+C*c.imag)
p/=(A+B+C)
r=distanceBetweenSegmentAndPoint(Line(a,b),p)
return Circle(p,r)
# 三角形の外心
def CircumscribedCircle(a:Point,b:Point,c:Point)->Circle:
p=(a-b)*norm(c)+(b-c)*norm(a)+(c-a)*norm(b)
p/=(a-b)*c.conjugate()+(b-c)*a.conjugate()+(c-a)*b.conjugate()
r=abs(p-a)
return Circle(p,r)
# 円Cと直線Lの交点
def CrossPoint_Circle_Line(C:Circle,L:Line)->List[Point]:
res=[]
d=distanceBetweenLineAndPoint(L,C.p)
if d>C.r+eps:
return res
h=projection(L,C.p)
if equal(d,C.r):
return [h]
e=unitVector(L.b-L.a)
ph=sqrt(C.r**2-d**2)
res.append(h-e*ph)
res.append(h+e*ph)
return res
# 2 円の交点
def CrossPointCircles(C1:Circle,C2:Circle)->List[Point]:
res=[]
mode=IsIntersectCircle(C1,C2)
d=abs(C1.p-C2.p)
if mode==4 or mode==0:
return res
if mode==3:
t=C1.r/(C1.r+C2.r)
res.append(C1.p+(C2.p-C1.p)*t)
return res
if mode==1:
if C2.r<C1.r-eps:
res.append(C1.p+(C2.p-C1.p)*(C1.r/d))
else:
res.append(C2.p+(C1.p-C2.p)*(C2.r/d))
return res
rc1=(C1.r**2+d**2-C2.r**2)/(2*d)
rs1=sqrt(C1.r**2-rc1**2)
if C1.r-abs(rc1)<eps:
rs1=0
e12=(C2.p-C1.p)/abs(C2.p-C1.p)
res.append(C1.p+rc1*e12+rs1*e12*point(0,1))
res.append(C1.p+rc1*e12+rs1*e12*point(0,-1))
return res
# 点pを通る円cの接線
def tangentToCircle(p:Point,c:Circle)->List[Point]:
return CrossPointCircles(c,Circle(p,sqrt(norm(c.p-p)-c.r**2)))
# 2円の共通接線
def tangent(c1:Circle,c2:Circle)->List[Line]:
res=[]
d=abs(c1.p-c2.p)
if equal(d,0):
return []
u=unitVector(c2.p-c1.p)
v=rotate(u,pi/2)
for s in [-1,1]:
h=(c1.r+c2.r*s)/d
if equal(h**2,1):
res.append(Line(c1.p+h*u*c1.r,c1.p+h*u*c1.r+v))
elif 1-h*h>0:
U=u*h
V=v*sqrt(1-h*h)
res.append(Line(c1.p+(U+V)*c1.r,c2.p-(U+V)*c2.r*s))
res.append(Line(c1.p+(U-V)*c1.r,c2.p-(U-V)*c2.r*s))
return res
def Dot(p,q):
res=0
for i in range(3):
res+=p[i]*q[i]
return res
def solve():
x1,y1,z1=map(int,input().split())
p1,q1=map(int,input().split())
x2,y2,z2=map(int,input().split())
p2,q2=map(int,input().split())
if p1*q2-q1*p2==0:
if Dot((x2-x1,y2-y1,z2-z1),(p1,q1,0))==0:
print(2)
else:
print(4)
return
if x1==x2 and y1==y2:
print(2)
return
A=point(x1,y1)
B=point(x1+q1,y1-p1)
C=point(x2,y2)
D=point(x2+q2,y2-p2)
L1=Line(A,B)
L2=Line(C,D)
CROSS=crossPoint(L1,L2)
P1=(x1,y1,z1)
P2=(x2,y2,z2)
M1=((x1+x2)/2,(y1+y2)/2,(z1+z2)/2)
R=0
for i in range(3):
R+=(P1[i]-M1[i])**2
Cx=CROSS.real
Cy=CROSS.imag
Mx=M1[0]
My=M1[1]
d=(Cx-Mx)**2+(Cy-My)**2
if d<R-eps:
print(3)
else:
print(4)
for _ in range(int(input())):
solve()
详细
Test #1:
score: 100
Accepted
time: 15ms
memory: 12056kb
input:
2 -1 -1 3 1 1 2 2 3 2 2 5 5 1 3 0 7 6 -2 1 -2
output:
4 3
result:
ok 2 number(s): "4 3"
Test #2:
score: 0
Accepted
time: 14ms
memory: 12136kb
input:
100 -13 -5 -7 -19 19 -19 -13 0 -7 15 -20 20 19 -17 18 20 -20 -1 18 -19 -18 15 -14 -19 18 19 -20 6 20 -19 -12 9 1 7 -16 -13 -14 -8 8 -13 -19 16 9 20 -19 19 -18 -11 19 -18 19 20 -8 12 20 -11 -9 18 -19 -18 8 11 -13 12 -18 18 13 8 4 -18 -16 20 17 -19 18 20 -18 -3 20 -19 -17 -20 -5 -18 -19 19 16 15 19 20...
output:
4 4 4 4 4 4 3 4 4 4 3 4 4 3 3 4 3 4 4 4 4 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 3 4 3 4 4 4 3 4 4 4 4 4 4 4 3 4 3 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 3 3 4 3 4 4 4 4 4 4 4 4 4
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 23ms
memory: 11952kb
input:
100 20 -9 -19 9 13 -12 14 -18 -17 12 2 -3 -2 2 -19 -8 9 -15 -19 3 -16 -16 -18 2 15 19 17 -6 -10 11 14 -20 -6 -19 7 -17 -8 -1 -7 -15 7 -15 3 2 13 -15 -9 11 15 2 -17 20 13 11 -8 -12 18 16 -18 -17 -17 15 -2 -20 1 8 -6 0 -16 -19 -5 -14 16 -17 10 -7 -16 17 -10 -13 1 1 -13 17 11 -3 -3 -18 4 -17 19 -6 -17 ...
output:
3 4 4 4 3 3 4 3 3 4 4 3 4 4 3 3 4 3 4 4 4 4 3 4 3 4 4 3 3 4 4 4 3 4 3 3 4 3 3 4 3 4 3 4 3 4 3 4 4 3 3 4 3 3 4 3 3 4 4 3 3 4 4 3 4 3 3 4 3 3 3 4 3 4 3 4 3 4 3 4 4 3 3 4 3 4 4 4 4 3 3 3 3 4 3 3 4 4 4 4
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 22ms
memory: 12136kb
input:
100 10 -9 -13 8 -7 -3 3 -15 -5 11 -14 -20 -17 13 -13 3 20 16 -20 8 -2 -15 -20 8 20 20 -10 15 12 6 4 2 20 14 14 -13 6 -20 -10 20 -18 -15 19 10 9 4 18 -11 -16 -15 20 -11 6 15 -10 -17 -19 -6 -6 8 -19 -19 -18 -11 -9 -6 4 18 11 -5 2 -18 20 0 -12 -10 -18 -17 20 -20 19 19 17 2 -11 -20 2 -16 -19 13 -6 6 -5 ...
output:
4 3 4 3 4 4 3 3 3 4 4 3 3 3 4 4 3 3 3 4 4 4 3 4 3 3 3 3 4 4 3 4 4 3 4 3 3 4 4 3 3 3 4 4 3 4 4 4 4 4 3 4 3 4 4 4 3 4 4 3 4 4 3 3 3 4 3 3 3 3 4 4 4 4 3 4 4 3 4 3 4 3 3 3 4 4 3 4 3 4 4 3 4 3 4 4 3 3 4 4
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 7ms
memory: 12072kb
input:
100 4 -19 -4 4 18 -15 20 -15 -16 18 -11 -10 -13 -7 14 20 -17 0 6 -20 -12 18 -8 3 -14 20 16 17 10 17 0 19 -17 -11 6 18 -19 -7 13 -13 -17 17 -17 -5 -1 17 -13 19 -10 -12 9 -3 -19 -12 -2 -16 11 13 12 -8 17 12 11 -1 20 13 -14 -5 -4 16 -20 8 -16 16 -3 9 -3 -6 14 -12 16 4 9 -16 -10 -15 -3 -17 -20 -2 20 2 1...
output:
4 4 3 4 3 4 4 4 4 4 3 4 3 4 3 3 4 3 3 4 3 4 3 3 4 4 4 4 4 3 3 4 3 4 3 4 4 4 4 4 3 4 4 4 3 4 4 4 4 4 4 4 4 3 4 4 4 4 4 3 3 3 4 4 4 4 4 3 3 4 3 4 4 4 4 3 4 4 3 4 3 4 3 4 4 4 4 4 4 3 4 3 4 4 4 4 3 4 4 4
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 19ms
memory: 12068kb
input:
100 -1 -13 -13 -14 -8 -1 -3 15 6 -14 19 -1 -16 -20 -14 -16 12 18 20 17 -19 17 -6 16 13 15 -8 18 16 10 17 20 0 0 -13 -19 -19 15 -14 -14 -11 -16 17 17 18 0 2 -10 20 -5 -8 -16 0 3 12 -19 0 -3 1 -14 -18 3 -12 -14 -15 20 1 17 20 -4 -20 6 20 20 -7 20 1 -9 -13 -4 2 17 -18 11 13 8 16 14 -12 16 -11 12 -20 0 ...
output:
3 4 4 4 3 4 4 4 3 4 4 4 3 4 3 4 3 4 3 3 4 4 3 3 3 4 4 4 3 3 4 4 4 3 4 4 4 4 3 3 4 4 4 4 4 4 3 4 4 3 3 3 4 3 3 4 4 4 3 4 4 3 3 3 3 4 4 4 4 3 3 3 4 4 3 4 3 3 4 3 3 4 3 4 4 3 3 3 4 4 3 3 4 3 3 3 3 3 4 3
result:
ok 100 numbers
Test #7:
score: 0
Accepted
time: 13ms
memory: 12024kb
input:
100 -16 0 17 16 16 16 -12 -16 14 12 19 -13 -20 -16 -8 -14 20 14 -6 -20 6 -19 12 18 -2 7 20 -19 3 -20 19 -5 12 -16 -12 -9 -11 0 19 4 11 -20 12 14 -14 -19 16 1 -12 -1 -8 -14 11 -15 2 9 -11 18 4 20 -14 3 -16 -20 -4 11 -16 7 -10 -11 20 16 -19 -10 8 -20 0 13 -17 -8 20 -17 2 14 -2 -17 13 7 -8 -11 -8 -6 -2...
output:
4 3 3 4 4 3 3 4 3 3 3 4 3 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 3 4 4 3 4 3 4 4 4 4 4 4 3 4 3 4 4 4 3 3 3 4 4 4 3 4 4 4 3 4 3 4 4 4 4 4 4 3 3 3 4 3 4 4 4 3 4 4 3 3 4 3 4 3 4 4 3 4 3 4 3 4 3 4 3 3 4 3 4
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 21ms
memory: 12004kb
input:
1 1 -1 1 1 1 1 1 2 -1 1
output:
3
result:
ok 1 number(s): "3"
Test #9:
score: 0
Accepted
time: 22ms
memory: 12024kb
input:
100 20 19 -6 18 19 -19 -20 14 19 20 -1 19 -19 6 18 12 -20 19 18 19 4 0 -18 -19 10 -13 12 7 -8 11 -19 -18 -9 -19 -20 18 20 11 18 19 -19 19 8 18 -19 18 -19 -12 -19 20 11 12 9 -15 -2 -12 -12 -4 3 11 -19 9 -10 -18 3 -3 -19 4 20 11 -19 -20 10 -20 -19 17 20 -10 19 18 -17 -20 14 19 20 17 20 -6 -18 -19 9 -1...
output:
4 4 4 4 4 4 3 4 4 3 4 4 4 4 3 4 4 3 4 4 4 4 3 4 4 4 4 3 4 4 3 4 4 3 3 4 4 4 4 4 4 4 4 4 4 3 4 4 3 4 3 4 4 4 4 3 3 4 4 4 3 3 4 4 3 4 3 3 4 3 4 3 4 4 4 4 4 4 4 3 4 4 3 4 4 3 4 4 4 4 4 4 4 4 4 3 4 4 4 4
result:
ok 100 numbers
Test #10:
score: 0
Accepted
time: 22ms
memory: 12020kb
input:
100 13 -13 12 5 12 12 20 14 -14 -8 18 -17 -5 -1 -17 -10 9 9 -10 18 13 -17 -1 19 -18 11 1 -2 -17 -18 16 19 -17 -8 6 -14 -1 16 -18 6 4 -14 18 -10 14 13 3 12 -1 -14 -20 1 -11 12 15 20 4 -20 -7 -17 8 -19 1 -9 -10 -19 8 -4 -17 18 6 -14 -12 -12 -5 -12 6 19 -18 -11 -16 -16 -10 15 16 12 18 -9 -17 16 -18 5 -...
output:
4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 4 3 4 3 3 4 4 4 4 4 4 3 3 3 3 3 3 3 3 4 3 4 3 4 4 4 4 4 3 4 3 3 4 4 3 3 3 3 3 4 3 3 3 3 3 3 3 3 3 3 4 4 4 4 3 4 3 4 4 4 4 3 4 4 3 3 3 3 4 4 4 4 3 4 3 4 4 3 4 4 4 4 4
result:
ok 100 numbers
Test #11:
score: 0
Accepted
time: 13ms
memory: 12092kb
input:
73 14 -7 7 1 10 -16 -4 11 1 10 -14 -13 -16 1 -8 -6 -12 -10 -2 16 -5 -10 -12 0 -13 15 -10 0 0 -2 19 20 19 17 -9 -14 -20 -15 -20 6 3 19 4 -16 -1 5 -13 11 -16 -1 -19 -20 -17 0 11 -19 -20 -10 2 -3 -9 -15 -18 1 -13 17 -13 -11 1 -13 10 -20 17 8 -1 15 20 1 16 -2 -20 -18 8 0 -11 12 -18 17 0 -10 -4 0 10 9 0 ...
output:
2 2 2 4 2 2 2 2 2 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 3 2 2 2 2 2 4 2 2 2 2 2 2 4 3 4 2 2 2 2 2 4 3 2 2 2 4 2 2 2 2 2 4 2 2 3 2 2
result:
ok 73 numbers
Test #12:
score: -100
Wrong Answer
time: 22ms
memory: 12056kb
input:
100 -20 -20 10 -1 1 20 20 10 -1 6 15 -19 12 -17 20 -18 20 10 17 15 7 -19 0 -16 13 18 17 -10 11 15 17 13 9 -16 15 -6 -13 14 -13 -20 -19 2 13 -8 13 20 -13 -12 -19 -8 -20 20 4 -11 -11 20 -20 4 10 -10 -12 3 0 12 -17 -14 20 17 12 17 6 -19 7 -11 -20 14 8 -6 17 -13 -12 10 -2 19 20 15 -15 -9 -20 3 4 19 -19 ...
output:
4 3 4 4 3 4 4 3 3 4 4 4 3 4 3 4 3 4 4 4 4 3 4 4 4 4 4 4 4 4 3 4 4 3 3 4 4 3 3 4 4 3 4 4 4 4 4 4 4 3 3 3 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 3 4 4 4 4 3 4 4 4 3 4 3 3 4 4 4 3 4 4 3
result:
wrong answer 4th numbers differ - expected: '3', found: '4'