結果

問題 No.2331 Maximum Quadrilateral
ユーザー navel_tosnavel_tos
提出日時 2023-05-29 22:11:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,241 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 90,624 KB
最終ジャッジ日時 2024-06-08 19:28:44
合計ジャッジ時間 6,781 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#MMA Contest 015 J

'''
4点を選び、面積の2倍を出力せよ。

2点を固定して、一番高さが出る点を2箇所選べばよさそう。凸包？しらんですね。

・2点(x1,y1), (x2,y2) を結ぶ直線の距離は
  y=(y2-y1)/(x2-x1) * (x-x1) + y1
  → (y2-y1)/(x2-x1) *x -y + (y2-y1)/(x2-x1)*(-x1)+y1 = 0

・(x3,y3)とax+by+c=0の距離は
  abs(a*x3 + b*y3 + c)/sqrt(a**2 + b**2)

これらの公式を用いて、距離の類推を行おう。
ところでこれ、absを外せばどちら側の距離か判定できたりしないかな？
できそうだな。

3点が与えられたときの三角形の面積(の2倍値)も関数化しておこう。
'''
tilt=lambda x1,y1,x2,y2: ((y2-y1)/(x2-x1),-1,(y2-y1)*(-x1)/(x2-x1)+y1)
dist=lambda A,B,C,x,y: (A*x+B*y+C)/(A**2 + B**2)**.5
area=lambda x1,y1,x2,y2,x3,y3: abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))
f=lambda:list(map(int,input().split()))

N=int(input()); Pos=[f() for _ in range(N)]; ans=0
for i in range(N):
    x1,y1=Pos[i]
    for j in range(i+1,N):
        x2,y2=Pos[j]
        if x1==x2:  #y座標が最も大きいものと、最も小さいものを採用 凹四角形に注意
            Candidate=sorted([(y,x,k) for k,(x,y) in enumerate(Pos) if k!=i and k!=j])
            y3,x3,k=Candidate[0]; y4,x4,L=Candidate[-1]
            if   y3<=y1<=y4: ans=max(ans,area(x1,y1,x2,y2,x3,y3)+area(x1,y1,x2,y2,x4,y4))
            else: ans=max(ans,abs(area(x1,y1,x2,y2,x3,y3)-area(x1,y1,x2,y2,x4,y4)))
        elif y1==y2:
            Candidate=sorted([(x,y,k) for k,(x,y) in enumerate(Pos) if k!=i and k!=j])
            x3,y3,k=Candidate[0]; x4,y4,L=Candidate[-1]
            if x3<=x1<=x4: ans=max(ans,area(x1,y1,x2,y2,x3,y3)+area(x1,y1,x2,y2,x4,y4))
            else: ans=max(ans,abs(area(x1,y1,x2,y2,x3,y3)-area(x1,y1,x2,y2,x4,y4)))
        else:
            A,B,C=tilt(x1,y1,x2,y2)
            Candidate=sorted([(dist(A,B,C,x,y),x,y,k)
                              for k,(x,y) in enumerate(Pos) if k!=i and k!=j])
            d3,x3,y3,k=Candidate[0]; d4,x4,y4,L=Candidate[-1]
            if d3<=0<=d4: ans=max(ans,area(x1,y1,x2,y2,x3,y3)+area(x1,y1,x2,y2,x4,y4))
            else: ans=max(ans,area(x1,y1,x2,y2,x3,y3)-area(x1,y1,x2,y2,x4,y4))
print(ans)
0