首页 > ACM题库 > HDU-杭电 > hdu 3211 Baking the Shaobing待解决[解题报告]C++
2014
03-06

hdu 3211 Baking the Shaobing待解决[解题报告]C++

Baking the Shaobing

问题描述 :

After LMY has been married to YY, YY lives in happiness, for LMY does all housework. When YY feels hungry, LMY cooks something for him to eat. When YY felt thirsty, LMY feeds him with water.

Now YY feels hungry again, so he asks LMY for food. But LMY is not at home. Fortunately, YY finds a piece of shaobing (a Chinese styled cake) in the kitchen.

This shaobing looks rather tempting. It has a shape of a simple polygon with N vertices, and its mess is evenly distributed. LMY had hung a string from the ceiling to the gravity center of the shaobing, so that the whole shaobing keeps balanced and lies in a horizontal plane although there is only one point hanging.

When YY starts to enjoy the shaobing, tragedy occurred… It is raw!

There is only one stove in the kitchen. Its cooking area lies in a horizontal plane and has a shape of a circle. YY has adjusted it to the same plane where the shaobing lies to cook it. The circle is centered at (x0, y0), with radius r. After turning on the stove, the part of the shaobing lying on the cooking area will be cooked.

However, the stove cannot be moved. So is the hanging point of the shaobing, or it may fall to the ground. The string can be moved, but YY cannot move it, because LMY has some special use with it. After all, YY can only rotate the shaobing by the hanging point.

YY is so hungry that he cannot wait for the whole shaobing to be cooked. He wants to rotate it to a best angle, cook it and then eat the cooked part, to comfort his stomach in a fastest way.

What angle should the shaobing be rotated to, so that the cooked part is the biggest?

输入:

The input contains several test cases. For each test case:

The first line consists of three integers x0, y0 and r, indicating the position and radius of the stove’s cooking area.

The second line contains an integer N (3<=N<=15), indicating the number of vertices of the shaobing.

In the third line there are N pairs of integers (x1, y1), (x2, y2), …, (xN, yN), indicating the coordinates of the vertices of the shaobing, in counterclockwise order.

All coordinates are in the range -1000 to 1000, inclusively.

There is a blank line separating test cases.

Input ends with a line where x0=y0=r=0, and this line should not be processed.

输出:

The input contains several test cases. For each test case:

The first line consists of three integers x0, y0 and r, indicating the position and radius of the stove’s cooking area.

The second line contains an integer N (3<=N<=15), indicating the number of vertices of the shaobing.

In the third line there are N pairs of integers (x1, y1), (x2, y2), …, (xN, yN), indicating the coordinates of the vertices of the shaobing, in counterclockwise order.

All coordinates are in the range -1000 to 1000, inclusively.

There is a blank line separating test cases.

Input ends with a line where x0=y0=r=0, and this line should not be processed.

样例输入:

0 0 1
3
0 0 1 0 0 1

0 0 0

样例输出:

0.5000