結果

問題 No.2331 Maximum Quadrilateral
ユーザー navel_tosnavel_tos
提出日時 2023-05-29 23:22:15
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,487 bytes
コンパイル時間 620 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 77,184 KB
最終ジャッジ日時 2024-06-08 19:39:50
合計ジャッジ時間 32,406 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,619 ms
76,416 KB
testcase_01 AC 951 ms
76,928 KB
testcase_02 AC 1,280 ms
76,544 KB
testcase_03 AC 1,118 ms
76,672 KB
testcase_04 AC 1,404 ms
76,544 KB
testcase_05 AC 1,499 ms
76,800 KB
testcase_06 AC 1,420 ms
76,544 KB
testcase_07 AC 1,286 ms
76,544 KB
testcase_08 AC 957 ms
76,800 KB
testcase_09 AC 873 ms
77,184 KB
testcase_10 AC 790 ms
76,544 KB
testcase_11 AC 859 ms
76,544 KB
testcase_12 AC 777 ms
76,992 KB
testcase_13 AC 821 ms
76,360 KB
testcase_14 AC 1,558 ms
76,544 KB
testcase_15 AC 190 ms
76,160 KB
testcase_16 AC 567 ms
76,416 KB
testcase_17 AC 104 ms
76,288 KB
testcase_18 AC 220 ms
76,672 KB
testcase_19 AC 127 ms
76,672 KB
testcase_20 AC 1,664 ms
76,672 KB
testcase_21 AC 1,657 ms
76,800 KB
testcase_22 AC 1,665 ms
76,672 KB
testcase_23 AC 1,695 ms
76,672 KB
testcase_24 AC 1,661 ms
76,672 KB
testcase_25 AC 38 ms
52,224 KB
testcase_26 AC 40 ms
52,864 KB
testcase_27 AC 39 ms
52,864 KB
testcase_28 AC 37 ms
52,480 KB
testcase_29 AC 36 ms
52,480 KB
testcase_30 WA -
testcase_31 AC 37 ms
52,480 KB
testcase_32 WA -
testcase_33 AC 36 ms
52,864 KB
testcase_34 AC 38 ms
52,608 KB
testcase_35 AC 40 ms
52,864 KB
testcase_36 AC 40 ms
52,608 KB
testcase_37 AC 41 ms
52,480 KB
testcase_38 AC 38 ms
52,736 KB
testcase_39 AC 36 ms
52,736 KB
testcase_40 AC 37 ms
52,736 KB
testcase_41 AC 38 ms
52,352 KB
testcase_42 AC 37 ms
52,864 KB
testcase_43 AC 37 ms
52,480 KB
testcase_44 AC 37 ms
52,608 KB
testcase_45 AC 36 ms
52,864 KB
testcase_46 WA -
権限があれば一括ダウンロードができます

ソースコード

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倍値)も関数化しておこう。

TLEして不貞腐れていたが、logNを落とせば通るっぽい。やろう。
'''
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座標が最も大きいものと、最も小さいものを採用 凹四角形に注意
            Lx,Ly,Hx,Hy=0,10**18,0,-10**18
            for k,(x,y) in enumerate(Pos):
                if k==i or k==j: continue
                if Ly>y: Lx,Ly=x,y
                if Hy<y: Hx,Hy=x,y
            if   Ly<=y1<=Hy: ans=max(ans,area(x1,y1,x2,y2,Lx,Ly)+area(x1,y1,x2,y2,Hx,Hy))
            else: ans=max(ans,abs(area(x1,y1,x2,y2,Lx,Ly)-area(x1,y1,x2,y2,Hx,Hy)))
        elif y1==y2:
            Lx,Ly,Hx,Hy=10**18,0,-10**18,0
            for k,(x,y) in enumerate(Pos):
                if k==i or k==j: continue
                if Lx>x: Lx,Ly=x,y
                if Hx<x: Hx,Hy=x,y
            if   Lx<=x1<=Hx: ans=max(ans,area(x1,y1,x2,y2,Lx,Ly)+area(x1,y1,x2,y2,Hx,Hy))
            else: ans=max(ans,abs(area(x1,y1,x2,y2,Lx,Ly)-area(x1,y1,x2,y2,Hx,Hy)))
        else:
            A,B,C=tilt(x1,y1,x2,y2); Ld,Lx,Ly,Hd,Hx,Hy=10**18,0,0,-10**18,0,0
            for k,(x,y) in enumerate(Pos):
                if k==i or k==j: continue
                d=dist(A,B,C,x,y)
                if Ld>d: Ld,Lx,Ly=d,x,y
                if Hd<d: Hd,Hx,Hy=d,x,y
            if Ld<=0<=Hd: ans=max(ans,area(x1,y1,x2,y2,Lx,Ly)+area(x1,y1,x2,y2,Hx,Hy))
            else: ans=max(ans,area(x1,y1,x2,y2,Lx,Ly)-area(x1,y1,x2,y2,Hx,Hy))
print(ans)
0