EppsNet Archive: Geometry

Competitive Programming: SPOJ – The Bulk!

ACM uses a new special technology of building its transceiver stations. This technology is called Modular Cuboid Architecture (MCA) and is covered by a patent of Lego company. All parts of the transceiver are shipped in unit blocks that have the form of cubes of exactly the same size. The cubes can be then connected to each other. The MCA is modular architecture, that means we can select preferred transceiver configuration and buy only those components we need . The cubes must be always connected “face-to-face”, i.e. the whole side of one cube is connected to the whole side of another cube. One cube can be thus connected to at most six other units. The resulting equipment, consisting of unit cubes is called The Bulk in the communication technology slang. Sometimes, an old and unneeded bulk is condemned, put into a storage place, and replaced with a new one. It… Read more →

Competitive Programming: SPOJ – Build the Fence

At the beginning of spring all the sheep move to the higher pastures in the mountains. If there are thousands of them, it is well worthwhile gathering them together in one place. But sheep don’t like to leave their grass-lands. Help the shepherd and build him a fence which would surround all the sheep. The fence should have the smallest possible length! Assume that sheep are negligibly small and that they are not moving. Sometimes a few sheep are standing in the same place. If there is only one sheep, it is probably dying, so no fence is needed at all … Input t [the number of tests <= 100] [empty line] n [the number of sheep <= 100000] x1 y1 [coordinates of the first sheep] … xn yn [integer coordinates from -10000 to 10000] [empty line] [other lists of sheep] Text grouped in [ ] does not appear in the input file.… Read more →

Competitive Programming: POJ 2074 – Line of Sight

Description An architect is very proud of his new home and wants to be sure it can be seen by people passing by his property line along the street. The property contains various trees, shrubs, hedges, and other obstructions that may block the view. For the purpose of this problem, model the house, property line, and obstructions as straight lines parallel to the x axis: Input Because each object is a line, it is represented in the input file with a left and right x coordinate followed by a single y coordinate: <x1> <x2> <y> where x1, x2, and y are non-negative real numbers, x1 < x2 . An input file can describe the architecture and landscape of multiple houses. For each house, the first line will have the coordinates of the house. The second line will contain the coordinates of the property line. The third line will have a… Read more →

Competitive Programming: POJ 2318 – TOYS

Description Calculate the number of toys that land in each bin of a partitioned toy box. Mom and dad have a problem – their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys. John’s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box. For this problem, you are asked to determine how many toys fall into each partition as John throws them into… Read more →

Competitive Programming: POJ 1905 – Expanding Rods

Description When a thin rod of length L is heated n degrees, it expands to a new length L’=(1+n*C)*L, where C is the coefficient of heat expansion. When a thin rod is mounted on two solid walls and then heated, it expands and takes the shape of a circular segment, the original rod being the chord of the segment. Your task is to compute the distance by which the center of the rod is displaced. Input The input contains multiple lines. Each line of input contains three non-negative numbers: the initial lenth of the rod in millimeters, the temperature change in degrees and the coefficient of heat expansion of the material. Input data guarantee that no rod expands by more than one half of its original length. The last line of input contains three negative numbers and it should not be processed. Output For each line of input, output one… Read more →

Competitive Programming: POJ 2084 – Game of Connections

Description This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n – 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect. It’s still a simple game, isn’t it? But after you’ve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? Input Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 < = n Read more →

Competitive Programming: POJ 2242 – The Circumference of the Circle

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 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 pi is approximately 3.141592653589793. Sample Input 0.0 -0.5… Read more →

Bernie Sanders is Wrong About Everything But He’s Raised the Intellectual Climate

Socialism has been discredited about as thoroughly as possible, but one thing I greatly admire about Bernie Sanders is this: He’s never made a political issue of the fact that he’s Jewish. He doesn’t say “It’s high time we had a Jewish president.” He doesn’t say “If you’re Jewish, you should vote for me because I’m Jewish.” And most importantly, he doesn’t dismiss criticism or critics as anti-Semitic. And because he doesn’t do any of the above, I don’t see his supporters or the media doing it either. It would be easy for him to do those things because it’s what people expect. Political discourse in America consists mainly of people calling each other racists, sexists, homophobes and bigots. It’s hard to complete a sentence without someone taking offense to a trigger word, a microaggression or a dog whistle. Abraham Lincoln once said this: If you have ever studied geometry,… Read more →