#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)