题解 | #游游的you矩阵#

冰冰的分界线

https://ac.nowcoder.com/acm/contest/93218/D

D题的另类体验

wa过的人都知道除法精度不够,有没有什么办法将除法转乘法呢?

求逆元!!!

比赛时取模数写错导致一直没过........

from math import inf
import sys
mod = int(1e9+7)

input = sys.stdin.readline

def inv(a,b):
    return a*pow(b,mod-2,mod)%mod

for _ in range(int(input())):
    n = int(input())
    vis = {}
    x = [*map(lambda x:int(x), input().split())]
    y = [*map(lambda x:int(x), input().split())]

    for i in range(n):
        for j in range(i + 1, n):
            dx = (x[i] - x[j])
            dy = (y[i] - y[j])
            k_ = 0

            if dx == 0:
                k_ = 0
            elif dy == 0:
                k_ = inf
            else:
                if dx>0 and dy>0:
                    k_ =  -inv(dx, dy)
                elif dx<0 and dy<0:
                    k_ =  -inv(-dx, -dy)
                else:k_ = inv(abs(dx),abs(dy))
            bx = (x[i] + x[j])
            by = (y[i] + y[j])

            if k_ == inf:
                if k_ in vis:
                    vis[k_].add(bx)
                else:
                    vis[k_]=set()
                    vis[k_].add(bx)
            elif k_==0:
                if k_ in vis:
                    vis[k_].add(by)
                else:
                    vis[k_] = set()
                    vis[k_].add(by)
            else:
                if k_ in vis:
                    vis[k_].add((mod + by - k_ * bx % mod) % mod)
                else:
                    vis[k_] = set()
                    vis[k_].add((mod + by - k_ * bx % mod) % mod)

    ans = 0
    for i in vis.values():
        ans +=len(i)
    print(ans)
全部评论
还真行
点赞 回复 分享
发布于 10-25 22:46 江西

相关推荐

6 收藏 评论
分享
牛客网
牛客企业服务