from epoint import *


class Corners:
  def __init__(self):
    self.corners=[]
  
  def add(self,x,y):
    a=EPoint(x,y)
    # for i,c in enumerate(self.corners): # move an improperly placed point
      # if a.dist(c)<20:
        # self.corners[i]=a
        # return
    
    if len(self.corners)<4: # add a new corner
      self.corners.append(a)
    
    if len(self.corners)<4: 
      return
    
    index,minDist=0,float('inf') # replace the corner closest to the clicked point
    for i,c in enumerate(self.corners):
      if a.dist(c)<minDist:
        index,minDist=i,a.dist(c)
    
    self.corners[index]=a
    self._canonizeOrder()
  
  
  ## Computes twice the area of a triangle formed by points a,b,c.
  #  
  #  @return positive value for points oriented counter-clockwise, negative for clockwise, zero for degenerate cases.
  def _doubleTriangleArea(a,b,c):
    return (a.x-b.x)*(c.y-a.y)-(c.x-a.x)*(a.y-b.y)
  
  def _slope(a,b):
    if(b.x==a.x): return float("inf")
    return (b.y-a.y)/(b.x-a.x)

    
  ## Order the corners (0,1,2,3) so they make a quadrangle with vertices KLMN in counter-clockwise order, K being in the upper left.
  #  
  #  For four points ABCD, there are 24 possible permutations corresponding to the desired KLMN.
  #  When we relax the condition of K being the upper left one, we get six groups of four equivalent permuations. KLMN ~ LMNK ~ MNKL ~ NKLM.
  #  
  #  xxxx -> KLMN | ABC | ABD | ACD | BCD | index | swap
  #  ------------ | :-: | :-: | :-: | :-: | ----: | ----
  #  A BCD        |  +  |  +  |  +  |  +  |    15 | 0
  #  A BDC        |  +  |  +  |  -  |  -  |    12 | CD
  #  A CBD        |  -  |  +  |  +  |  -  |     6 | BC
  #  A CDB        |  -  |  -  |  +  |  +  |     3 | AB
  #  A DBC        |  +  |  -  |  -  |  +  |     9 | AD
  #  A DCB        |  -  |  -  |  -  |  -  |     0 | BD
  #  
  #  For every non-degenerate quadrangle, there must be 1-3 edges going right-left (from a higher to a lower x coordinate).
  #  From these pick the one with the lowest slope (dy/dx) and declare its ending point the upper left corner. For the same slope pick the one further left.
  #  
  #  @return True for a convex quadrangle, False for concave or degenerate cases.
  def _canonizeOrder(self):
    if len(self.corners)!=4: return False # erroneus call
    
    a,b,c,d=(x for x in self.corners)
    abc=Corners._doubleTriangleArea(a,b,c)
    abd=Corners._doubleTriangleArea(a,b,d)
    acd=Corners._doubleTriangleArea(a,c,d)
    bcd=Corners._doubleTriangleArea(b,c,d)
    
    if any(x==0 for x in (abc,abd,acd,bcd)): return False # collinear degenerate
    
    swaps=[(1,3),(0,1),(1,2),(0,3),(2,3),(0,0)]
    index=(8 if abc>0 else 0)+(4 if abd>0 else 0)+(2 if acd>0 else 0)+(1 if bcd>0 else 0)
    if index%3!=0: return False # concave degenerate
    swap=swaps[index//3]
    
    self.corners[swap[0]], self.corners[swap[1]] = self.corners[swap[1]], self.corners[swap[0]] # counter-clockwise order
    
    kIndex=None
    lowestSlope=float("inf")
    
    for i,corner in enumerate(self.corners): # find the NK edge: going right-left with the lowest slope, secondarily the one going down
      ii=(i+1)%4
      slope=abs(Corners._slope(corner,self.corners[ii]))
      if corner.x>self.corners[ii].x and (slope<lowestSlope or (slope==lowestSlope and corner.y<self.corners[ii].y)):
        kIndex=ii
        lowestSlope=slope
    
    self.corners=self.corners[kIndex:]+self.corners[:kIndex] # rotate the upper left corner to the first place
        
    return True # success

# import itertools
# points=[(10,8),(8,10),(12,10),(10,12)]
# for perm in itertools.permutations(points):
  # corn=Corners()
  # for p in perm: corn.add(p[0],p[1])
  # print(corn._canonizeOrder())
  # print(corn.corners)