denseform(n, coeff)={
  local(f); f = vector(n);
  for(i=1, matsize(coeff)[1], f[coeff[i,1]]+=coeff[i,2]);
  f;
}

\\ inequality t_{ij} > t_{ik}, that is, (k-j)v_i + (i-k) v_j + (j-i) v_k > 0
\\ (for i < j < k)
collideright(n, i,j,k)=denseform(n, [i, k-j; j, i-k; k, j-i]);
collideleft(n, i,j,k) =-collideright(n, i,j,k);
collide(n, i,j) = denseform(n, [i,1;j,-1]);
notcollide(n, i,j) = -collide(n, i, j);

ineq(s)={
  local(l, d, depth, match, R);
  l=Vec(s); depth=vector(#l); d=0;
  for(i=1, #l, depth[i]=d; d+=(l[i]=="(")-(l[i]==")"));
  match=vector(#l);
  for(i=1, #l, if(l[i]=="(", for(j=i+1, #l,
    if(depth[j]==depth[i]+1 && l[j]==")", match[i]=j; match[j]=i; next (2)))));

  R=[];
  for(i1=1,#l,
    if (l[i1] == "(", j1=match[i1];
      \\ (): v_i > v_j
      R = concat(R, [collide(#l, i1, j1)]);
      \\ (())
      for (i2=i1+1, j1-1, if (l[i2] == "(", j2=match[i2];
        R = concat (R,
          [collideright (#l, i1, i2, j2), collideleft (#l, i2, j2, j1)])));
      \\ ()()
      for (i2=j1+1, #l, if (l[i2] == "(", j2=match[i2];
        R = concat (R,
          [collideleft (#l, i1, j1, i2), collideright (#l, j1, i2, j2)])))
    , if (l[i1] != ")", \\ escaped bullet
      \\ !! and !()
      for (i2=i1+1, #l, if (l[i2]!=")",
        R = concat (R, [notcollide (#l, i1, i2)])));
      \\ ()!  (!! already done)
      for (i2=1, i1-1, if (l[i2]==")",
        R = concat (R, [notcollide (#l, i2, i1)])));
    ))
  );
  R;
}
polytope(s)={
  local(R); R=ineq(s);
  concat([vector(#R, i, vector(#s+1,j,if(j<=#s, R[i][j]))),
    vector(#s,i, vector(#s+1,j, j==i)),
    vector(#s,i, vector(#s+1,j, (j>#s)-(j==i)))]);
}