Given a polygon of n points (not necessarily convex), your goal is to say whether there is a circle of a given a radius R that contains the polygon or not.
The input consists of several input cases. The first line of each input case is the number n (with n < 100) of vertices in the polygon. Then you are given n lines each containing a couple of integers that define the coordinates of the vertices. The last line of the input case will be a real number indicating the radius R of the circle.
The end of the input will be signaled by an input case with n = 0 vertices, that must not be processed.
You may assume that no vertex will appear twice in any given input case.
If the polygon can be packed in a circle of the given radius you have to print:
The polygon can be packed in the circle.
If the polygon cannot be packed you have to print:
There is no way of packing that polygon.
範例輸入 1
3 0 0 1 0 0 1 1.0 3 0 0 1 0 0 1 0.1 0
範例輸出 1
The polygon can be packed in the circle. There is no way of packing that polygon.
Pro 專屬功能: 查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.