回答 1 已采纳 Description
Long long ago, there were several identical columns (or cylinders) built vertically in a big open space near Yokohama (Fig. 1). In the daytime, the shadows of the columns were moving on the ground as the sun moves in the sky. Each column was very tall so that its shadow was very long. The top view of the shadows is shown in Fig. 2.
Fig. 1: Columns (or cylinders)
Fig. 2: Top view of the columns (Fig. 1) and their shadows
The directions of the sun that minimizes and maximizes the widths of the shadows of the columns were said to give the important keys to the secrets of ancient treasures.
The width of the shadow of each column is the same as the diameter of the base disk. But the width of the whole shadow (the union of the shadows of all the columns) alters according to the direction of the sun since the shadows of some columns may overlap those of other columns.
Fig. 3 shows the direction of the sun that minimizes the width of the whole shadow for the arrangement of columns in Fig. 2.
Fig. 3: The direction of the sun for the minimal width of the whole shadow
Fig. 4 shows the direction of the sun that maximizes the width of the whole shadow. When the whole shadow is separated into several parts (two parts in this case), the width of the whole shadow is defined as the sum of the widths of the parts.
Fig. 4: The direction of the sun for the maximal width of the whole shadow
A direction of the sun is specified by an angle θ defined in Fig. 5. For example, the east is indicated by θ=0, the south by θ=π/2, and the west by θ=π. You may assume that the sun rises in the east (θ=0) and sets in the west (θ=π).
Your job is to write a program that, given an arrangement of columns, computes two directions θmin and θmax of the sun that give the minimal width and the maximal width of the whole shadow, respectively.
The position of the center of the base disk of each column is specified by its (x,y) coordinates. The x-axis and y-axis are parallel to the line between the east and the west and that between the north and the south, respectively. Their positive directions indicate the east and the north, respectively.
You can assume that the big open space is a plane surface.
Fig. 5: The definition of the angle of the direction of the sun
There may be more than one θmin or θmax for some arrangements in general, but here, you may assume that we only consider the arrangements that have unique θmin and θmax in the range 0<=θmin<π, 0<=θmax<π.
Input
The input consists of multiple datasets, followed by the last line containing a single zero.
Each dataset is formatted as follows.
n
x1 y1
x2 y2
...
xn yn
n is the number of the columns in the big open space. It is a positive integer no more than 100.
xk and yk are the values of x-coordinate and y-coordinate of the center of the base disk of the k-th column (k=1, ..., n). They are positive integers no more than 30. They are separated by a space.
Note that the radius of the base disk of each column is one unit (the diameter is two units). You may assume that some columns may touch each other but no columns overlap others.
For example, a dataset
3
1 1
3 1
4 3
corresponds to the arrangement of three columns depicted in Fig. 6. Two of them touch each other.
Fig. 6: An arrangement of three columns
Output
For each dataset in the input, two lines should be output as specified below. The output lines should not contain extra characters such as spaces.
In the first line, the angle θmin, the direction of the sun giving the minimal width, should be printed. In the second line, the other angle θmax, the direction of the sun giving the maximal width, should be printed.
Each angle should be contained in the interval between 0 and π (abbreviated to [0, π]) and should not have an error greater than ε=0.0000000001 (=10-10).
When the correct angle θ is in [0,ε], approximate values in [0,θ+ε] or in [π+θ-ε, π] are accepted. When the correct angle θ is in [π-ε, π], approximate values in [0, θ+ε-π] or in [θ-ε, π] are accepted.
You may output any number of digits after the decimal point, provided that the above accuracy condition is satisfied.
Sample Input
3
1 1
3 1
4 3
4
1 1
2 3
3 8
1 9
8
1 1
3 1
6 1
1 3
5 3
1 7
3 5
5 5
8
20 7
1 27
30 14
9 6
17 13
4 2
17 7
8 9
0
Sample Output
2.553590050042226
0.982793723247329
1.570796326794896
2.819842099193151
1.325817663668032
2.094395102393196
2.777613697080149
0.588002603547568
回答 2 已采纳 问题描述 :
You are responsible for inspecting the trees located in a park, to make sure they remain healthy. The location of each tree is given to you as a point in the twodimensional plane, distinct from that of every other tree. Due to recentlyreplanted grass, you are only allowed to walk through the park along a collection of paths. Each path is described by an infinite-length horizontal or vertical line in the two-dimensional plane. No tree lies on any path.
You are concerned that it may not be possible to view all the trees in the park from the paths. In particular, a tree is visible only if you can view it by standing on some path while facing in a direction perpendicular to that path; there must be no intervening tree that obstructs your view. Given the geometrical configuration of the park, please report the number of visible trees.
输入:
There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths.
The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers.
The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case.
End of the input is signified by a line with two space-separated 0′s.
输出:
There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths.
The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers.
The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case.
End of the input is signified by a line with two space-separated 0′s.
样例输入:
6 3
-1 3
4 2
6 2
6 3
6 4
4 3
x=0
y=-1
y=5
1 2
2 3
x=5
y=5
0 0
样例输出:
5
1
回答 1 已采纳 A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 <= x, y <= 5 with lines from the origin to the visible points.
Write a program which, given a value for the size, N, computes the number of visible points (x,y) with 0 <= x, y <= N.
Input
The first line of input contains a single integer C, (1 <= C <= 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer N, (1 <= N <= 1000), which is the size.
Output
For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.
Sample Input
4
2
4
5
231
Sample Output
1 2 5
2 4 13
3 5 21
4 231 32549
回答 1 已采纳 Description
There is a number of disjoint vertical line segments in the plane. We say that two segments are horizontally visible if they can be connected by a horizontal line segment that does not have any common points with other vertical segments. Three different vertical segments are said to form a triangle of segments if each two of them are horizontally visible. How many triangles can be found in a given set of vertical segments?
Task
Write a program which for each data set:
reads the description of a set of vertical segments,
computes the number of triangles in this set,
writes the result.
Input
The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 <= d <= 20. The data sets follow.
The first line of each data set contains exactly one integer n, 1 <= n <= 8 000, equal to the number of vertical line segments.
Each of the following n lines consists of exactly 3 nonnegative integers separated by single spaces:
yi', yi'', xi - y-coordinate of the beginning of a segment, y-coordinate of its end and its x-coordinate, respectively. The coordinates satisfy 0 <= yi' < yi'' <= 8 000, 0 <= xi <= 8 000. The segments are disjoint.
Output
The output should consist of exactly d lines, one line for each data set. Line i should contain exactly one integer equal to the number of triangles in the i-th data set.
Sample Input
1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
Sample Output
1