题解 | #公切线#
公切线
https://ac.nowcoder.com/acm/contest/84773/E
E题遍历两个正方形的各顶点即可,当恰有一个顶点重合时公切线有无限条,注意需要唯一表示直线方程,如果用Ax+By+C=0表示需考虑约分,此处直接使用两两比值的元组表示,分母为零时取None值
from itertools import product
from fractions import Fraction
def square(x1,y1,x2,y2):
yield x1,y1
yield x2,y2
cx,cy = Fraction(x1+x2,2),Fraction(y1+y2,2)
for x,y in ((x1,y1),(x2,y2)):
yield cx+cy-y,x-cx+cy
def cross(x1,y1,x2,y2):
return x1*y2-x2*y1
def div(x,y):
return Fraction(x,y) if y else None
def parse(x1,y1,x2,y2):
# u*x+v*y+w == 0
u = y2-y1
v = x1-x2
w = -x1*u-y1*v
return div(u,v),div(v,w),div(u,w)
def main():
for _ in range(int(input())):
x1,y1,x2,y2,x3,y3,x4,y4 = map(int,input().split())
s1 = list(square(x1,y1,x2,y2))
s2 = list(square(x3,y3,x4,y4))
if sum((u1,v1) == (u2,v2) for (u1,v1),(u2,v2) in product(s1,s2)) == 1:
print("Infinity"); continue
ans = set()
for (u1,v1),(u2,v2) in product(s1,s2):
if (u1,v1) == (u2,v2): continue
du,dv = u2-u1,v2-v1
for s in (s1,s2):
signs = [cross(du,dv,x-u1,y-v1) for x,y in s]
if not (all(sign >= 0 for sign in signs)\
or all(sign <= 0 for sign in signs)): break
else: ans.add(parse(u1,v1,u2,v2))
print(len(ans))
main()
查看5道真题和解析