QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#638889#9227. Henry the Plumberucup-team3646#WA 22ms12184kbPython39.2kb2024-10-13 17:13:352024-10-13 17:13:35

Judging History

你现在查看的是最新测评结果

  • [2024-10-13 17:13:35]
  • 评测
  • 测评结果:WA
  • 用时:22ms
  • 内存:12184kb
  • [2024-10-13 17:13:35]
  • 提交

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
  
  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()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 12072kb

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: 17ms
memory: 11956kb

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: 19ms
memory: 12104kb

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: 12184kb

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: 21ms
memory: 12084kb

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: 11956kb

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: 16ms
memory: 12020kb

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: 20ms
memory: 11988kb

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: 12084kb

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: 16ms
memory: 12180kb

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: -100
Wrong Answer
time: 17ms
memory: 12084kb

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
3
2
2
2
3
2
2
2
4
3
3
2
3
3
3
2
2
2
2
2
2
3
2
3
2
2
3
2
2
2
3
2
3
2
3
3
4
2
2
2
2
3
3
4
3
4
2
2
2
3
2
4
3
2
2
2
4
3
3
2
3
3
4
2
2
3
2
3

result:

wrong answer 6th numbers differ - expected: '2', found: '3'