#875916 (PyPy3) No.2331 Maximum Quadrilateral

提出ソース

結果

問題	No.2331 Maximum Quadrilateral
ユーザー	navel_tos
提出日時	2023-05-30 03:03:05
言語	PyPy3 (7.3.15)
結果	AC
実行時間	84 ms / 2,000 ms
コード長	6,265 bytes
コンパイル時間	297 ms
コンパイル使用メモリ	86,780 KB
実行使用メモリ	75,172 KB
最終ジャッジ日時	2023-08-28 00:22:13
合計ジャッジ時間	5,611 ms
ジャッジサーバーID （参考情報）	judge12 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	78 ms 70,772 KB
testcase_01	AC	77 ms 71,180 KB
testcase_02	AC	78 ms 71,204 KB
testcase_03	AC	83 ms 75,020 KB
testcase_04	AC	80 ms 74,984 KB
testcase_05	AC	84 ms 75,104 KB
testcase_06	AC	80 ms 71,124 KB
testcase_07	AC	78 ms 71,060 KB
testcase_08	AC	79 ms 74,872 KB
testcase_09	AC	77 ms 70,764 KB
testcase_10	AC	79 ms 74,820 KB
testcase_11	AC	76 ms 71,264 KB
testcase_12	AC	77 ms 71,176 KB
testcase_13	AC	74 ms 71,044 KB
testcase_14	AC	77 ms 70,996 KB
testcase_15	AC	74 ms 71,260 KB
testcase_16	AC	76 ms 71,052 KB
testcase_17	AC	73 ms 70,884 KB
testcase_18	AC	74 ms 71,176 KB
testcase_19	AC	71 ms 70,980 KB
testcase_20	AC	80 ms 70,884 KB
testcase_21	AC	80 ms 71,112 KB
testcase_22	AC	84 ms 74,948 KB
testcase_23	AC	82 ms 75,172 KB
testcase_24	AC	79 ms 71,096 KB
testcase_25	AC	69 ms 70,904 KB
testcase_26	AC	70 ms 71,176 KB
testcase_27	AC	69 ms 71,060 KB
testcase_28	AC	68 ms 71,220 KB
testcase_29	AC	69 ms 71,136 KB
testcase_30	AC	69 ms 70,904 KB
testcase_31	AC	71 ms 70,872 KB
testcase_32	AC	70 ms 71,052 KB
testcase_33	AC	69 ms 71,000 KB
testcase_34	AC	70 ms 71,148 KB
testcase_35	AC	69 ms 71,180 KB
testcase_36	AC	69 ms 71,280 KB
testcase_37	AC	68 ms 70,904 KB
testcase_38	AC	68 ms 71,136 KB
testcase_39	AC	69 ms 71,232 KB
testcase_40	AC	70 ms 70,980 KB
testcase_41	AC	70 ms 71,048 KB
testcase_42	AC	68 ms 71,116 KB
testcase_43	AC	67 ms 70,996 KB
testcase_44	AC	69 ms 71,172 KB
testcase_45	AC	68 ms 71,216 KB
testcase_46	AC	68 ms 71,088 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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を落とせば通るっぽい。やろう。
→だめでした。PyPy3ではO(N^3)は切られるみたいです。

とりゐさんが解説記事を書いてくださっていました
やはり凸包で考えないとだめだよね、の気持ち かなし
Reference: https://toriidao.hateblo.jp/entry/2023/05/29/231655

気合いを入れて凸包を勉強する。
典型041の解説スライドに凸包があったので、これを読んで前処理しよう。
外積が正なら反時計回り、負なら時計回り。
Reference: https://twitter.com/e869120/status/1393753066331992065/photo/1

めちゃくちゃ沢山WAが出た。原因は凹四角形のとき、凸包を構成する因子が減ってしまう事。
例えばテストケース: small20は凹四角形であり、凸包の頂点は3点だけとなる。
4
0 0
3 0
4 3
4 -3

原因がわかった。凸包を構成する因子が3つしかないときは、凸包3点+それ以外の1点 の
四角形が最適だった。この場合を例外処理する。

それでも答えが合わないが、三分探索では3択までしか絞り込めない？様子。
手動で押し切ることにした。
'''

#関数定義
area=lambda x1,y1,x2,y2,x3,y3: abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))
opro=lambda x1,y1,x2,y2: x1*y2-x2*y1
f=lambda:list(map(int,input().split()))

#入力受取
N=int(input()); Pos=sorted([f() for _ in range(N)]); R=[]

#凸包を求める  opro: 2次元ベクトルの外積を算出する
for x,y in Pos:
    while len(R)>1:
        x1,y1=R[-2]; x2,y2=R[-1]
        if opro(x2-x1,y2-y1,x-x2,y-y2)>=0: R.pop()
        else: break
    R.append((x,y))
T=len(R)
for x,y in Pos[-2::-1]:
    while len(R)>T:
        x1,y1=R[-2]; x2,y2=R[-1]
        if opro(x2-x1,y2-y1,x-x2,y-y2)>=0: R.pop()
        else: break
    R.append((x,y))
R.pop()

#凸包上の点が3点だけのときは、内部の点も採用した4点の凹四角形が最善となる。
#(凸包2点 + 内部の点)の三角形のうち面積最小のものを選ぶ
if len(R)==3:
    CH=set(R); minS=10**18; x1,y1=R[0]; x2,y2=R[1]; x3,y3=R[2]
    for x,y in Pos:
        if (x,y) in CH: continue
        minS=min(minS,area(x1,y1,x2,y2,x,y),area(x2,y2,x3,y3,x,y),area(x3,y3,x1,y1,x,y))
    print(area(x1,y1,x2,y2,x3,y3)-minS); exit()

#凸包を三分探索
Pos=R; N=len(Pos); R=Pos+Pos; ans=0
for i in range(N):
    for j in range(i+2,N):
        x1,y1=Pos[i]; x2,y2=Pos[j]
        #i<k<j となる凸包を探す
        Lt,Rt=i+1,j-1
        while abs(Lt-Rt)>2:
            midL,midR=(Lt*2+Rt)//3,(Lt+Rt*2)//3; xL,yL=Pos[midL]; xR,yR=Pos[midR]
            SL,SR=area(x1,y1,x2,y2,xL,yL),area(x1,y1,x2,y2,xR,yR)
            Lt,Rt=(midL,Rt) if SL<=SR else (Lt,midR)
        #三択まで絞れたら、どれが優れているか決める
        xL,yL=Pos[Lt]; xM,yM=Pos[(Lt+Rt)//2]; xR,yR=Pos[Rt]
        SL,SM,SR=area(x1,y1,x2,y2,xL,yL),area(x1,y1,x2,y2,xM,yM),area(x1,y1,x2,y2,xR,yR)
        Upper=Lt if SL==max(SL,SM,SR) else (Lt+Rt)//2 if SM==max(SL,SM,SR) else Rt

        #反対側の区間の凸包を探す
        Ni=i+N; Lt,Rt=j+1,Ni-1
        if Ni-j<2: continue
        while abs(Lt-Rt)>2:
            midL,midR=(Lt*2+Rt)//3,(Lt+Rt*2)//3; xL,yL=R[midL]; xR,yR=R[midR]
            SL,SR=area(x1,y1,x2,y2,xL,yL),area(x1,y1,x2,y2,xR,yR)
            Lt,Rt=(midL,Rt) if SL<=SR else (Lt,midR)
        xL,yL=R[Lt]; xM,yM=R[(Lt+Rt)//2]; xR,yR=R[Rt]
        SL,SM,SR=area(x1,y1,x2,y2,xL,yL),area(x1,y1,x2,y2,xM,yM),area(x1,y1,x2,y2,xR,yR)
        Lower=Lt if SL==max(SL,SM,SR) else (Lt+Rt)//2 if SM==max(SL,SM,SR) else Rt

        #答えを更新
        xH,yH=R[Upper]; xL,yL=R[Lower]
        ans=max(ans,area(x1,y1,x2,y2,xH,yH)+area(x1,y1,x2,y2,xL,yL))
print(ans)

'''
■ここからO(N^3)解法。 N>=350からTLE
from collections import deque as dq
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)
'''

yukicoder

結果

テストケース

ソースコード