結果

問題 No.1041 直線大学
ユーザー uni_pythonuni_python
提出日時 2020-06-21 14:32:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 7,061 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 87,344 KB
実行使用メモリ 78,272 KB
最終ジャッジ日時 2023-09-16 18:21:29
合計ジャッジ時間 5,992 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 71 ms
71,172 KB
testcase_01 AC 71 ms
71,376 KB
testcase_02 AC 71 ms
71,264 KB
testcase_03 AC 69 ms
71,364 KB
testcase_04 AC 77 ms
71,548 KB
testcase_05 AC 70 ms
71,520 KB
testcase_06 AC 83 ms
75,688 KB
testcase_07 AC 113 ms
77,540 KB
testcase_08 AC 101 ms
77,572 KB
testcase_09 AC 101 ms
77,784 KB
testcase_10 AC 139 ms
78,120 KB
testcase_11 AC 135 ms
78,244 KB
testcase_12 AC 130 ms
78,272 KB
testcase_13 AC 93 ms
76,648 KB
testcase_14 AC 103 ms
77,248 KB
testcase_15 AC 91 ms
76,884 KB
testcase_16 AC 101 ms
77,364 KB
testcase_17 AC 99 ms
77,844 KB
testcase_18 AC 102 ms
77,488 KB
testcase_19 AC 108 ms
77,436 KB
testcase_20 AC 75 ms
71,512 KB
testcase_21 AC 106 ms
77,560 KB
testcase_22 AC 70 ms
71,168 KB
testcase_23 AC 111 ms
77,972 KB
testcase_24 AC 107 ms
77,468 KB
testcase_25 AC 117 ms
77,872 KB
testcase_26 AC 92 ms
76,800 KB
testcase_27 AC 99 ms
77,404 KB
testcase_28 AC 69 ms
71,124 KB
testcase_29 AC 70 ms
71,004 KB
testcase_30 AC 70 ms
71,672 KB
testcase_31 AC 69 ms
71,576 KB
testcase_32 AC 68 ms
71,008 KB
testcase_33 AC 69 ms
71,496 KB
testcase_34 AC 69 ms
71,388 KB
testcase_35 AC 70 ms
71,316 KB
testcase_36 AC 71 ms
71,316 KB
testcase_37 AC 71 ms
71,280 KB
testcase_38 AC 130 ms
77,572 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input=sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
mod=10**9+7

def main():
    import cmath
    import itertools
    import math
    import sys


    sys.setrecursionlimit(10 ** 9)
    IINF = 10 ** 18
    MOD = 10 ** 9 + 7
    # MOD = 998244353


    INF = float("inf")
    PI = cmath.pi
    TAU = cmath.pi * 2
    EPS = 1e-10


    class Point:
        """
        2次元空間上の点
        """

        # 反時計回り側にある
        CCW_COUNTER_CLOCKWISE = 1
        # 時計回り側にある
        CCW_CLOCKWISE = -1
        # 線分の後ろにある
        CCW_ONLINE_BACK = 2
        # 線分の前にある
        CCW_ONLINE_FRONT = -2
        # 線分上にある
        CCW_ON_SEGMENT = 0

        def __init__(self, x: float, y: float):
            self.c = complex(x, y)
            
        @property
        def x(self):
            return self.c.real

        @property
        def y(self):
            return self.c.imag

        @staticmethod
        def from_complex(c: complex):
            return Point(c.real, c.imag)

        @staticmethod
        def from_polar(r: float, phi: float):
            c = cmath.rect(r, phi)
            return Point(c.real, c.imag)

        def __add__(self, p):
            """
            :param Point p:
            """
            c = self.c + p.c
            return Point(c.real, c.imag)

        def __iadd__(self, p):
            """
            :param Point p:
            """
            self.c += p.c
            return self

        def __sub__(self, p):
            """
            :param Point p:
            """
            c = self.c - p.c
            return Point(c.real, c.imag)

        def __isub__(self, p):
            """
            :param Point p:
            """
            self.c -= p.c
            return self

        def __mul__(self, f: float):
            c = self.c * f
            return Point(c.real, c.imag)

        def __imul__(self, f: float):
            self.c *= f
            return self

        def __truediv__(self, f: float):
            c = self.c / f
            return Point(c.real, c.imag)

        def __itruediv__(self, f: float):
            self.c /= f
            return self

        def __repr__(self):
            return "({}, {})".format(round(self.x, 10), round(self.y, 10))

        def __neg__(self):
            c = -self.c
            return Point(c.real, c.imag)

        def __eq__(self, p):
            return abs(self.c - p.c) < EPS

        def __abs__(self):
            return abs(self.c)

        @staticmethod
        def ccw(a, b, c):
            """
            線分 ab に対する c の位置
            線分上にあるか判定するだけなら on_segment とかのが速い
            :param Point a:
            :param Point b:
            :param Point c:
            """
            b = b - a
            c = c - a
            det = b.det(c)
            if det > EPS:
                return Point.CCW_COUNTER_CLOCKWISE
            if det < -EPS:
                return Point.CCW_CLOCKWISE
            if b.dot(c) < -EPS:
                return Point.CCW_ONLINE_BACK
            if c.norm() - b.norm() > EPS:
                return Point.CCW_ONLINE_FRONT
            return Point.CCW_ON_SEGMENT

        def dot(self, p):
            """
            内積
            :param Point p:
            :rtype: float
            """
            return self.x * p.x + self.y * p.y

        def det(self, p):
            """
            外積
            :param Point p:
            :rtype: float
            """
            return self.x * p.y - self.y * p.x

        def dist(self, p):
            """
            距離
            :param Point p:
            :rtype: float
            """
            return abs(self.c - p.c)

        def norm(self):
            """
            原点からの距離
            :rtype: float
            """
            return abs(self.c)

        def phase(self):
            """
            原点からの角度
            :rtype: float
            """
            return cmath.phase(self.c)

        def angle(self, p, q):
            """
            p に向いてる状態から q まで反時計回りに回転するときの角度
            -pi <= ret <= pi
            :param Point p:
            :param Point q:
            :rtype: float
            """
            return (cmath.phase(q.c - self.c) - cmath.phase(p.c - self.c) + PI) % TAU - PI

        def area(self, p, q):
            """
            p, q となす三角形の面積
            :param Point p:
            :param Point q:
            :rtype: float
            """
            return abs((p - self).det(q - self) / 2)

        def projection_point(self, p, q, allow_outer=False):
            """
            線分 pq を通る直線上に垂線をおろしたときの足の座標
            :param Point p:
            :param Point q:
            :param allow_outer: 答えが線分の間になくても OK
            :rtype: Point|None
            """
            diff_q = q - p
            # 答えの p からの距離
            r = (self - p).dot(diff_q) / abs(diff_q)
            # 線分の角度
            phase = diff_q.phase()

            ret = Point.from_polar(r, phase) + p
            if allow_outer or (p - ret).dot(q - ret) < EPS:
                return ret
            return None

        def reflection_point(self, p, q):
            """
            直線 pq を挟んで反対にある点
            :param Point p:
            :param Point q:
            :rtype: Point
            """
            # 距離
            r = abs(self - p)
            # pq と p-self の角度
            angle = p.angle(q, self)
            # 直線を挟んで角度を反対にする
            angle = (q - p).phase() - angle
            return Point.from_polar(r, angle) + p

        def on_segment(self, p, q, allow_side=True):
            """
            点が線分 pq の上に乗っているか
            :param Point p:
            :param Point q:
            :param allow_side: 端っこでギリギリ触れているのを許容するか
            :rtype: bool
            """
            if not allow_side and (self == p or self == q):
                return False
            # 外積がゼロ: 面積がゼロ == 一直線
            # 内積がマイナス: p - self - q の順に並んでる
            return abs((p - self).det(q - self)) < EPS and (p - self).dot(q - self) < EPS
    
    N=I()
    P=[]
    for i in range(N):
        x,y=MI()
        p=Point(x,y)
        P.append(p)
        
    ans=0
    for i in range(N):
        for j in range(N):
            if i!=j:
                temp=0
                for k in range(N):
                    if P[k].on_segment(P[i],P[j]):
                        temp+=1
                ans=max(ans,temp)
            
            
    print(ans)
                    
                
    


main()
0