| Problem description | | Progress |
|
Темы:
Computational geometry
Another winter has come in a flat country, and we urgently need to switch to winter time! The problem is that the hand of the city clock (the only one, by the way) located at the origin is very, very heavy, and therefore the workers want to know which way to turn the hand will be faster. To make things easier for you, they have already figured out where the arrow is pointing and where it should point. Help them!
Input
The first line specifies the point where the arrow is pointing. It is specified by the coordinates X1 and Y1 (\(- 10 <= X_1, Y_1 <= 10\)).
The second line specifies the point where the arrow should point. It is specified by X2 and Y2 coordinates (\(- 10 <= X2, Y2 <= 10\)).
Coordinates are given by the real type.
Output
On a single line print "Clockwise" if the arrow needs to be rotated clockwise, "Counter-clockwise" if it needs to be rotated counterclockwise , and "Doesn't matter", if it takes the same time, in which direction it would not be twisted. Phrases should be displayed without quotes.
Examples
| # |
Input |
Output |
| 1 |
10
-1 1
|
Counterclockwise |
| |
![]()
|
|
Темы:
Computational geometry
A miracle happened! The long-awaited Half-Life 3, which millions of people around the world dreamed of, is finally out! Vasya was also looking forward to the continuation of the legendary series, and did not even eat in the school cafeteria for a whole month, so that he would have enough to buy this masterpiece! The only problem that stands in his way is a huge algebra homework assignment. In class, he went through a new topic - straight lines, and now he needs to do as many as N tasks on building a straight line through 2 points. But you really want to play, and the next day tell your friends what a cool graphic there is ... Therefore, he asked you, his friend, to help him.
Input
The first line contains the coordinates of the first point (X1, Y1), (\(-50 <= X_1, Y_1 <= 50\)).
The second line contains the coordinates of the second point (X2, Y2), (\(-50 <= X_2, Y_2 <= 50\)).
Output
On a single line print 3 integers in a row: the coefficients a, b, c of the equation of a straight line.
Note: if your task doesn't work, but you are sure that everything is correct, try multiplying all coefficients by -1. The task assumes that you have used formulas taken from the lecture/theory.
Examples
| # |
Input |
Output |
| 1 |
-1 -1
1 1
|
-2 2 0 |
| |
![]()
|
|
Темы:
Computational geometry
Venceslav recently read a new pickup book and now he wants to test his knowledge in the park. For simplicity, let's imagine the park as a set of paths, which are segments on a plane. Wenceslas has already walked in this park, and he knows which girl is walking along which path. The problem is that Wenceslas is very lazy and only walks along one path. And he is also too lazy to find out what kind of girls he can meet along the way, and therefore he asked You, his best friend, to help him in this difficult matter.
Input
The first line contains the coordinates of the ends of the path (X1, Y1) and ( X2, Y2), along which Wenceslas walks (\(- 20 <= X1, Y1, X2, Y2 <= 20\)).
The second line contains an integer N - the number of paths the girls walk along (\(0 <= N <= 5\)< /span>).
In the following N lines, enter the coordinates of the ends of the paths along which the girls walk (Xi1, Yi1< /sub>) and (Xi2, Yi2), by i -th path walking i-th girl (\(-20 <= X_{i1}, Y_{i1}, X_{i2 }, Y_{i2} <= 20\))
Output
In the first line print the number M - the number of girls whose paths will intersect with the path of Wenceslas (touching the paths is considered an intersection).
In the second line print M numbers - numbers of girls our hero will meet. Girls are numbered starting from one!
Examples
| # |
Input |
Output |
| 1 |
0 0 2 2
1
0 2 2 0
|
1
1 |
| |
![]()
|
|
Темы:
Computational geometry
Input
Six numbers – coordinates of the three vertices of the triangle.
Output
Single number – the area of the triangle.
Examples
| # |
Input |
Output |
| 1 |
1 1 2 4 3 2 |
2.50000 |
| |
![]()
|
|
Темы:
Computational geometry
Input
Six numbers – the coordinates of the point and the coordinates of the start and end of the vector.
Output
One line “ YES” if the point belongs to the ray defined by the vector and “ NO” otherwise.
Examples
| # |
Input |
Output |
| 1 |
4 0 4 2 4 5 |
NO |
| |
![]()
|
|
Темы:
Computational geometry
In order to replenish the budget and save fuel, the new mayor of the town of Glupov decided to conduct a campaign to combat left-handed slopes and left-handed flights. To do this, he banned drivers from making left turns, setting a fine for each left turn in the amount of one million (a U-turn is not considered a left turn).
From a difficult past, Glupov inherited streets that can intersect at any angle. The mayor ordered the installation of a computer system of total surveillance that monitors each car, recording its coordinates every time it changes direction (including the start and end points of the path).
It is required to write a program that calculates, from the recorded sequence of car coordinates, a fine to be collected from the driver.
Input
The first line contains an integer N - the number of pairs of coordinates written (\(1 <= N <= 1000\) ). Each of the following N lines contains the next of these pairs (real numbers).
Output
Display the driver's total fine in millions.
Examples
| # |
Input |
Output |
| 1 |
4
0 0
10
1 1
2 1
|
1 |
| |
![]()
|
|
Темы:
Computational geometry
Freken Bok is at the point \(A(x_a, y_a)\) and looking straight at the Kid standing at the point \(B(x_b, y_b)\) asks the question: "Which ear is my buzzing in?". Naturally, the formidable housekeeper is buzzing in her ear, because at the point \(C(x_c, y_c)\) Carlson hovered with the engine on. Decide which Kid's answer is correct.
Input
The coordinates of points A, B and C are entered from the keyboard. The initial data are integers, modulo not exceeding 1000.
Output
Print the word LEFT (in capital letters) if the housekeeper's left ear is buzzing, RIGHT – if on the right, BOTH – if buzzing in both left and right is the same.
Examples
| # |
Input |
Output |
| 1 |
0 0 1 0 0 1 |
LEFT |
| |
![]()
|
|
Темы:
Computational geometry
Two numbers are given - the coordinates of a point that does not coincide with the origin. Find the polar coordinates of a point that does not coincide with the origin.
Input
The input string contains two integers, the coordinates of the point. The numbers are integers, modulo not exceeding 1000.
Imprint
One number is the value of its polar angle (in radians). The value of the polar angle must belong to the interval [0; 2*π).
Examples
| # |
Input |
Output |
| 1 |
2 3 |
0.98279 |
| |
![]()
|
|
Темы:
Computational geometry
Once the evil wizard Sarumyan looked into the video chat and saw a system of N mirrors there. He thought for a long time before an inner voice told him that the system was not simple. He realized that if you look at this system from a certain angle, and see a given point A through all N mirrors (that is, so that his gaze is reflected through each of them exactly once, and then hit point A), then they will open all the secrets of the Internet to him.
However, the forces of light did not doze off and, through the agent network, found out everything about this video chat.
It is required to write a program that would tell the forces of light from what angle they need to look at the system of mirrors in order to find out all the secrets of the Internet.
Input:
The first line of the input file contains a single number – number of mirrors (0<N≤10). The next line contains the coordinates (x and y, where the x-axis is directed to the right, the y-axis – up) of the starting point (where you need to look at the mirrors) and point A. Next, N lines contain information about the mirrors – four numbers each, indicating the coordinates of the beginning and end of the mirror. The reflective surface is located on the left side of the mirror (when viewed from the first point towards the second). Mirrors are transparent on the reverse side.
Moreover, the following restrictions are met:
All coordinates are real and do not exceed 10000 in absolute value
No mirrors intersect
End and start points do not lie on any of the mirrors
Output:
The first line of the output file must be written YES if the solution exists, and NO if not. If there is a solution, then in the second line you need to write down the angle in degrees (with an accuracy of six decimal places), under which you need to look at the mirrors. The angle is counted counterclockwise from the Ox axis and ranges from 0 to 360 degrees.
Examples
| # |
Input |
Output |
| 1 |
2
0 0
05
1 0 1 2
-1 4 –1 2 |
YES
51.340192 |
| |
![]()
|
|
Темы:
Computational geometry
Ternary search
The Ministry of Road Transport has decided to build a new office for itself. Since the minister regularly goes out to inspect the most important routes, it was decided that the office of the ministry should not be located too far from them.
The most important alignments are straight lines on the plane. The Ministry wants to choose a location for its office so that the maximum distance from the office to the highways is as short as possible.
You need to write a program that, given the location of the most important highways, determines the optimal location of the house for the office of the Ministry of Road Transport.
Input
The first line of the input file contains a single integer n — number of most important traces (1 ≤ n ≤ 104 ).
The next n lines describe the traces. Each trace is described by four integers x1, y1, x2 and y2 and is a straight line passing through the points (x1, y1) and (x2, y2) . The coordinates of the given points do not exceed 104 in absolute value. Dots (x1 , y1) and (x2 , y2) do not match for any line.
Output
The output file should contain two space-separated real numbers: the coordinates of the point where the office of the Ministry of Road Transport should be built. Modulo coordinates must not exceed 109, it is guaranteed that at least one such answer exists. If there are several optimal answers, print any of them.
The answer must have an absolute or relative error of no more than 10−6, which means the following. Let the maximum distance from the drawn point to some trace be equal to x, and in the correct answer it is equal to y. The answer will be counted if the value of the expression | x .minus; y | / max(1, |y| ) does not exceed 10−6.
| Input |
Output |
|
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
|
0.5000000004656613 0.4999999995343387 |
|
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
|
4040.9996151750674 12003.999615175067 |
Personal Olympiad, All-Russian Olympiad for schoolchildren, Regional stage, 2011, 2nd day, Problem D
| |
![]()
|