| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 7416 | The Circumference of the Circle |
|
| 7418 | Eeny Meeny Moo |
|
| 7427 | Globetrotter |
|
| 7444 | Anagram Groups |
|
| 7465 | The Sierpinski Fractal |
|
Description
To calculate the circumference of a circle seems to be an easy task - provided you know its diameter. But what if you don't?
You are given the cartesian coordinates of three non-collinear points in the plane. Your job is to calculate the circumference of the unique circle that intersects all three points.
Input
The input file will contain one or more test cases. Each test case consists of one line containing six real numbers x1, y1, x2, y2, x3, y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file.
Output
For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of π is approximately 3.141592653589793.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow. To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the country in a systematic, totally fair manner. Germany's cities were enumerated randomly from 1 to n. Freiburg was number 1, Ulm was number 2, Karlsruhe was number 3, and so on in a purely random order. Then a number m would be picked at random, and Internet access would first be cut off in city 1 (clearly the fairest starting point) and then in every mth city after that, wrapping around to 1 after n, and ignoring cities already cut off. For example, if n = 17 and m = 5, net access would be cut off to the cities in the order [1, 6, 11, 16, 5, 12, 2, 9, 17, 10, 4, 15, 14, 3, 8, 13, 7]. The problem is that it is clearly fairest to cut off Ulm last (after all, this is where the best programmers come from), so for a given n, the random number m needs to be carefully chosen so that city 2 is the last city selected.
Your job is to write a program that will read in a number of cities n and then determine the smallest integer m that will ensure that Ulm can surf the net while the rest of the country is cut off.
Input
The input file will contain one or more lines, each line containing one integer n with 3 ≤ n < 150, representing the number of cities in the country. Input is terminated by a value of zero (0) for n.
Output
For each line of the input, print one line containing the integer m fulfilling the requirement specified above.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
As a member of an ACM programming team you'll soon find yourself always traveling around the world: Zürich, Philadelphia, San José, Atlanta,... from 1999 on the Contest Finals even will be on a different continent each year, so one day you might get to Japan or Australia.
At the contest site it would be interesting to know how many miles you are away from home. For this sake, your job is to write a program to compute the geographical distance between two given locations on the Earth's surface.
We assume that the Earth is a perfect sphere with a radius of exactly 6378 km. The geographical distance between A and B is the length of the geodetic line segment connecting A and B.
The geodetic line segment between two points on a sphere is the shortest connecting curve lying entirely in the surface of the sphere.
The value of pi is approximately 3.141592653589793.
Input
The input file will consist of two parts: a list of cities and a list of queries.
City List
The city list consists of up to 100 lines, one line per city. Each line will contain a string ci and two real numbers lati and longi, representing the city name, its latitude and its longitude, respectively.
The city name will be shorter than 30 characters and will not contain white-space characters.
The latitude will be between -90 (South Pole) and +90 (North Pole). The longitude will be between -180 and +180 where negative numbers denote locations west of the meridian and positive numbers denote locations east of the meridian. (The meridian passes through Greenwich, London.)
The city list will be terminated by a line consisting of a single "#".
Query List
Each line will contain two city names A and B.
The query list will be terminated by the line "# #".
Output
For each query, print a line saying "A - B" where A and B are replaced by the city names. Then print a line saying x km" where x is replaced by the geographical distance (in km) between the two cities, rounded to the nearest integer.
If one of the cities in the query didn't occur in the city list, print a line saying "Unknown" instead. Print a blank line after each query.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
World-renowned Prof. A. N. Agram's current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups.
A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.
Input
The input contains words composed of lowercase alphabetic characters, separated by whitespace. It is terminated by EOF.
Output
Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider a regular triangular area, divide it into four equal triangles of half height and remove the one in the middle. Apply the same operation recursively to each of the three remaining triangles. If we repeated this procedure infinite times, we'd obtain something with an area of zero. The fractal that evolves this way is called the Sierpinski Triangle. Although its topological dimension is 2, its Hausdorff-Besicovitch dimension is log(3)/log(2)~1.58, a fractional value (that's why it is called a fractal). By the way, the Hausdorff-Besicovitch dimension of the Norwegian coast is approximately 1.52, its topological dimension being 1.
For this problem, you are to outline the Sierpinski Triangle up to a certain recursion depth, using just ASCII characters. Since the drawing resolution is thus fixed, you'll need to grow the picture appropriately. Draw the smallest triangle (that is not divided any further) with two slashes, to backslashes and two underscores like this:
/
/__
To see how to draw larger triangles, take a look at the sample output.
Input
The input contains several testcases. Each is specified by an integer n. Input is terminated by n=0. Otherwise 1<=n<=10 indicates the recursion depth.
Output
For each test case draw an outline of the Sierpinski Triangle with a side's total length of 2n characters. Align your output to the left, that is, print the bottom leftmost slash into the first column. The output must not contain any trailing blanks. Print an empty line after each test case.
http://poj.org/problem?id=1941
連結