#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] #i2: 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 Hyx: Lx,Ly=x,y if Hxd: Ld,Lx,Ly=d,x,y if Hd