結果

問題 No.1041 直線大学
コンテスト
ユーザー uni_python
提出日時 2020-06-21 14:32:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 117 ms / 2,000 ms
コード長 7,061 bytes
コンパイル時間 284 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 76,672 KB
最終ジャッジ日時 2024-11-16 08:05:11
合計ジャッジ時間 3,925 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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