Unless you have some additional structure on the points $A_1$,...,$A_n$ your problem is as hard (and as easy) as computing the convex hull of $2n$ points in $\mathbb{R}^n$, and triangulating this convex hull. 

EDIT:

Neither the fact that you have zeroes nor the value of the determinant simplify the problem, as far as I can see.

The way I think about your problem is as follows. Using projective coordinates, you have $2n$ vectors $(A_1,1),\dots, (A_n,1), (e_1,0),\dots, (e_n,0)$ in $\mathbb R^{n+1}$ and want to compute its positive hull and a triangulation (in the sense of vector configurations) of it. If you prefer to live in the affine world, you can multiply the last $n$ vectors by $d+1$ so that all your vectors (now points) lie in the affine space $\sum x_i = d+1$. In this sense, as I said in my original answer, your problem becomes that of computing a convex hull (Q1) and a triangulation (Q2) of $2n$ points in $\mathbb R^n$.

If you are interested in arbitrary $n$ I think there is not much more I can say other than "use the general machinery". But if you are interested in small $n$ there are two things you can do to get a lower dimensional "picture" of your problem:

- Cayley Trick: your configuration is a Cayley configuration, meaning that your $2n$ points lie in two parallel hyperplanes. What the Cayley Trick says is that in these conditions you only need to look at what happens at an intermediate hyperplane, where what you have is a Minkowski sum of two $(n-1)$-simplices. Triangulations of your polytope become (and are in bijection to) fine mixed subdivisions of this Minkowski sum of two $(n-1)$-simplices.

- Gale transform: the Gale transform of $2n$ points in affine $n$-space is $2n$-vectors in $\mathbb R^{n-1}$. In a Gale transform you can "read" both the convex hull and the triangulations of your original polytope. 

You can learn more about both aspects in [my book on Triangulations][1] (Section 9.2 for the Cayley Trick, Sections 4.1 and 5.4, among others, for Gale transforms and their relation to triangulations.


  [1]: http://www.springer.com/mathematics/geometry/book/978-3-642-12970-4