
ZOJ Problem Set  1971
Computer scientists live on pizza. Now the doctors say this is no good. We ought to eat more balanced. So you put your really large pizza onto your table and eat slicebyslice carefully watching that the rest of your meal stays where it is  on the table. Since computer scientists love pizza, their favourite table is shaped like a slice of pizza. However, different people may have differentsized tables. Everyone has his own preference for the number of slices a pizza has to be cut to. However, all agree that the slices must have identical size. Write a program to help the poor pizza lovers!
The input file contains several test cases. Each test case starts with the number of slices n the pizza is cut to. Input is terminated by n = 0. Otherwise, 1 <= n <= 10. Then follow 9 floatingpoint numbers px, py, r, tx, ty, ux, uy, vx, vy specifying the coordinates of the center p of the pizza, its radius, and the coordinates of three points t, u, v. They define the three corners of the sliceshaped table in counterclockwise order, with t being the center. The pizza is a homogeneous twodimensional circular object. There is always a cut from its center parallel to the xaxis towards increasing xvalues. The remaining pizza stays connected during the whole process, no matter what slices are removed. The distances from t to u, v are equal except for very small rounding errors. Tables are never larger than a halfcircle.
For each test case output on a line theordering of slices, so that during the whole process of eating the pizza it does not fall down the table. Slices are numbered counterclockwise starting with 1 directly above the positive xaxis. If several such ordering exist, choose the lexicographically first one. If no ordering of slices exists, so that the pizza does not fall down, output a line containing the word "impossible" instead. Remark A connected, rigid, flat object remains fixed on a convex, flat surface if and only if the object's center of gravity lies above the surface. The xcoordinate, for example, of the center of gravity of an object s can be calculated by (��sxds) / (��sds). Likewise, the ycoordinate can be expressed as (��syds) / (��sds). Note that the denominator of these expressions gives the area of s.
2 (3.0,1.0) 1.0 (3.0,1.1) (1.5,0.4) (4.5,0.4)
2 1 Source: University of Ulm Local Contest 2002 