L3/M1, 2005–2006

Algorithmique effective – TD 7 Géométrie, encore et toujours

1 Un polygone dans un cercle

Exercice 1 Packing polygons. UVa : 10005. 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. Input

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. Output

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.

Sample Input

3
0 0
1 0
0 1
1.0
3
0 0
1 0
0 1
0.1
0

Sample Output

The polygon can be packed in the circle.
There is no way of packing that polygon.

2 Les points les plus proches

Exercice 2 The closest pair problem. PC : 111402 ; UVa : 10245.

Given a set of points in a two dimensional space, you will have to find the distance between the closest two points. Input

The input file contains several sets of input. Each set of input starts with an integer N (0 ≤ N ≤ 10000), which denotes the number of points in this set. The next N lines contain the coordinates of N two-dimensional points. The first of the two numbers denotes the X-coordinate and the latter denotes the Y -coordinate. The input is terminated by a set whose N = 0. This set should not be processed. The value of the coordinates will be less than 40000 and non-negative. Output

For each set of input produce a single line of output containing a floating point number (with four digits after the decimal point) which denotes the distance between the closest two points. If there is no such two points in the input whose distance is less than 10000, print the line INFINITY. Sample Input

3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
0

Sample Output

INFINITY
36.2215

3 Encore privé de dessert

Pas de DM pour cette fois-ci non plus ! (On se rattrapera plus tard…)