結果

問題 No.1041 直線大学
ユーザー Coki628Coki628
提出日時 2020-05-05 18:16:01
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 832 ms / 2,000 ms
コード長 6,462 bytes
コンパイル時間 98 ms
コンパイル使用メモリ 13,440 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-11-16 08:01:30
合計ジャッジ時間 7,791 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 30 ms
11,392 KB
testcase_01 AC 31 ms
11,520 KB
testcase_02 AC 31 ms
11,392 KB
testcase_03 AC 32 ms
11,520 KB
testcase_04 AC 32 ms
11,520 KB
testcase_05 AC 33 ms
11,648 KB
testcase_06 AC 32 ms
11,392 KB
testcase_07 AC 39 ms
11,520 KB
testcase_08 AC 41 ms
11,520 KB
testcase_09 AC 44 ms
11,520 KB
testcase_10 AC 758 ms
11,520 KB
testcase_11 AC 744 ms
11,520 KB
testcase_12 AC 768 ms
11,648 KB
testcase_13 AC 63 ms
11,648 KB
testcase_14 AC 390 ms
11,648 KB
testcase_15 AC 94 ms
11,520 KB
testcase_16 AC 289 ms
11,520 KB
testcase_17 AC 37 ms
11,520 KB
testcase_18 AC 136 ms
11,648 KB
testcase_19 AC 301 ms
11,520 KB
testcase_20 AC 29 ms
11,648 KB
testcase_21 AC 154 ms
11,520 KB
testcase_22 AC 31 ms
11,520 KB
testcase_23 AC 688 ms
11,520 KB
testcase_24 AC 365 ms
11,520 KB
testcase_25 AC 177 ms
11,520 KB
testcase_26 AC 49 ms
11,520 KB
testcase_27 AC 86 ms
11,520 KB
testcase_28 AC 32 ms
11,392 KB
testcase_29 AC 32 ms
11,392 KB
testcase_30 AC 30 ms
11,520 KB
testcase_31 AC 32 ms
11,392 KB
testcase_32 AC 28 ms
11,392 KB
testcase_33 AC 28 ms
11,392 KB
testcase_34 AC 29 ms
11,392 KB
testcase_35 AC 28 ms
11,392 KB
testcase_36 AC 29 ms
11,392 KB
testcase_37 AC 30 ms
11,392 KB
testcase_38 AC 832 ms
11,520 KB
testcase_39 AC 70 ms
11,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class Geometry:
    """ 幾何学計算用クラス """

    def __init__(self, EPS):
        self.EPS = EPS

    def add(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1+x2, y1+y2)

    def sub(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return (x1-x2, y1-y2)

    def mul(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1*b, y1*b)
        x2, y2 = b 
        return (x1*x2, y1*y2)

    def div(self, a, b):
        x1, y1 = a
        if not isinstance(b, tuple):
            return (x1/b, y1/b)
        x2, y2 = b
        return (x1/x2, y1/y2)

    def abs(self, a):
        from math import hypot
        x1, y1 = a
        return hypot(x1, y1)

    def norm(self, a):
        x, y = a
        return x**2 + y**2

    def dot(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*x2 + y1*y2

    def cross(self, a, b):
        x1, y1 = a
        x2, y2 = b
        return x1*y2 - y1*x2

    def project(self, seg, p):
        """ 線分segに対する点pの射影 """

        p1, p2 = seg
        base = self.sub(p2, p1)
        r = self.dot(self.sub(p, p1), base) / self.norm(base)
        return self.add(p1, self.mul(base, r))

    def reflect(self, seg, p):
        """ 線分segを対称軸とした点pの線対称の点 """

        return self.add(p, self.mul(self.sub(self.project(seg, p), p), 2))

    def ccw(self, p0, p1, p2):
        """ 線分p0,p1から線分p0,p2への回転方向 """

        a = self.sub(p1, p0)
        b = self.sub(p2, p0)
        # 反時計回り
        if self.cross(a, b) > self.EPS: return 1
        # 時計回り
        if self.cross(a, b) < -self.EPS: return -1
        # 直線上(p2 => p0 => p1)
        if self.dot(a, b) < -self.EPS: return 2
        # 直線上(p0 => p1 => p2)
        if self.norm(a) < self.norm(b): return -2
        # 直線上(p0 => p2 => p1)
        return 0

    def intersect(self, seg1, seg2):
        """ 線分seg1と線分seg2の交差判定 """

        p1, p2 = seg1
        p3, p4 = seg2
        return (
            self.ccw(p1, p2, p3) * self.ccw(p1, p2, p4) <= 0
            and self.ccw(p3, p4, p1) * self.ccw(p3, p4, p2) <= 0
        )
    
    def get_distance_PP(self, p1, p2):
        from math import hypot

        x1, y1 = p1
        x2, y2 = p2
        return hypot(x1-x2, y1-y2)

    def get_distance_LP(self, line, p):
        """ 直線lineと点pの距離 """

        p1, p2 = line
        return abs(self.cross(self.sub(p2, p1), self.sub(p, p1)) / self.abs(self.sub(p2, p1)))

    def get_distance_SP(self, seg, p):
        """ 線分segと点pの距離 """

        p1, p2 = seg
        if self.dot(self.sub(p2, p1), self.sub(p, p1)) < 0: return self.abs(self.sub(p, p1))
        if self.dot(self.sub(p1, p2), self.sub(p, p2)) < 0: return self.abs(self.sub(p, p2))
        return self.get_distance_LP(seg, p)

    def get_distance_SS(self, seg1, seg2):
        """ 線分seg1と線分seg2の距離 """

        p1, p2 = seg1
        p3, p4 = seg2
        if self.intersect(seg1, seg2): return 0
        return min(
            self.get_distance_SP(seg1, p3), self.get_distance_SP(seg1, p4),
            self.get_distance_SP(seg2, p1), self.get_distance_SP(seg2, p2),
        )

    def get_cross_pointSS(self, seg1, seg2):
        """ 線分seg1と線分seg2の交点 """

        p1, p2 = seg1
        p3, p4 = seg2
        base = self.sub(p4, p3)
        dist1 = abs(self.cross(base, self.sub(p1, p3)))
        dist2 = abs(self.cross(base, self.sub(p2, p3)))
        t = dist1 / (dist1+dist2)
        return self.add(p1, self.mul(self.sub(p2, p1), t))
    
    def intersectCL(self, c, line):
        """ 円cと直線lineの交差判定 """

        x, y, r = c
        return self.get_distance_SP(line, (x, y)) <= r

    def get_cross_pointCL(self, c, line):
        """ 円cと直線lineの交点 """
        from math import sqrt

        if not self.intersectCL(c, line): return -1
        x, y, r = c
        p1, p2 = line
        pr = self.project(line, (x, y))
        e = self.div(self.sub(p2, p1), self.abs(self.sub(p2, p1)))
        base = sqrt(r*r - self.norm(self.sub(pr, (x, y))))
        return [self.add(pr, self.mul(e, base)), self.sub(pr, self.mul(e, base))]
    
    def arg(self, p):
        from math import atan2
        x, y = p
        return atan2(y, x)
    
    def polar(self, a, r):
        from math import sin, cos
        return (cos(r)*a, sin(r)*a)
    
    def intersectCC(self, c1, c2):
        """ 円c1と円c2の交差判定 """
        from math import hypot

        x1, y1, r1 = c1
        x2, y2, r2 = c2
        return hypot(x1-x2, y1-y2) <= r1 + r2
    
    def get_cross_pointCC(self, c1, c2):
        """ 円c1と円c2の交点 """
        from math import acos

        if not self.intersectCC(c1, c2): return -1
        x1, y1, r1 = c1
        x2, y2, r2 = c2
        try:
            d = self.abs(self.sub((x1, y1), (x2, y2)))
            a = acos((r1*r1+d*d-r2*r2) / (2*r1*d))
            t = self.arg(self.sub((x2, y2), (x1, y1)))
            return [self.add((x1, y1), self.polar(r1, t+a)), self.add((x1, y1), self.polar(r1, t-a))]
        except:
            # 一方が他方を内包しちゃってる場合等はここに飛ぶ(はず)
            return -1

N = INT()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((x, y))

gm = Geometry(EPS)
ans = 2
for i in range(N):
    x1, y1 = XY[i]
    for j in range(i+1, N):
        x2, y2 = XY[j]
        line = ((x1, y1), (x2, y2))
        cnt = 2
        for k in range(N):
            if k == i or k == j:
                continue
            x3, y3 = XY[k]
            if gm.get_distance_LP(line, (x3, y3)) < EPS:
                cnt += 1
        ans = max(ans, cnt)
print(ans)
0