Участник:Ujify/bearandshuffles

Материал из DISCOPAL
Перейти к: навигация, поиск

task: https://www.codechef.com/viewsolution/46705329

from collections import defaultdict,Counter
from operator import itemgetter
 
n=int(input().strip())
 
 
P=[]
 
def cross(p,q,r):
    return ( (p[0]-q[0])*(r[1]-q[1]) - (p[1]-q[1])*(r[0]-q[0]) )
 
U,L=[],[]
def makeconvex(P):
    global U,L
    U,L=[],[]
    sz=len(P)
    for i in range(sz):
        while ( (len(U)>=2) and (cross(U[len(U)-2],U[len(U)-1],P[i])<=0) ):
            U.pop()
        U.append(P[i])
    for i in range(sz):
        while ( (len(L)>=2) and (cross(L[len(L)-2],L[len(L)-1],P[i])>=0) ):
            L.pop()
        L.append(P[i])
def dist(p1,p2):
    return (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
def FindAllPodal_And_GetMaxPair():
    global U,L
    ans=0
    P,Q=0,0
    sizeU=len(U)
    sizeL=len(L)
    i,j=0,sizeL-1
    #print(sizeU,sizeL)
    while j>0 or i<sizeU-1:
        tmpdist = dist(U[i],L[j])
        #print(tmpdist,i,j)
        if tmpdist>ans:
            P=i
            Q=j
            ans=tmpdist
        if i==sizeU-1:
            j-=1
        elif j==0:
            i+=1
        elif ( (U[i+1][1]-U[i][1])*(L[j][0]-L[j-1][0]) > (U[i+1][0]-U[i][0])*(L[j][1]-L[j-1][1]) ):
            i+=1
        else:
            j-=1
        #print("---->>>",i,j)
    return [U[P][2],L[Q][2]]
ans=[0]*750005
def main():
    global ans
    for i in range(1,n+1):
        x,y=map(int,input().strip().split())
        P.append([x,y,i])
    while(P.__len__()>1):
        size=len(P)
        tmp=P[:]
        tmp.sort(key=itemgetter(0,1))
        makeconvex(tmp)
        #print(U,"\n",L)
        res = FindAllPodal_And_GetMaxPair()
        #print(res)
        maxx=max(res)
        #print(maxx)
        disT=dist(P[res[0]-1],P[res[1]-1])
        #print(disT,"<<<----")
        for i in range(maxx,size+1):
            ans[i]=disT
        count=size-maxx+1
        while count:
            count-=1
            P.pop()
    print(0)
    for i in range(2,n+1):
        print(ans[i])
if __name__ == '__main__':
    main()
"""
 
5
20 20
40 30
35 35
0 10
-170 1000000000
 
"""
 


StasFomin 16:06, 21 мая 2021 (MSK): TLE, может кому-нибудь удастся улучшить.

Bearandshuffles 2021-05-21 16-06-25 image0.png