Competitive Programming: POJ 2074 – Line of Sight


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:

POJ 2074 - Line of Sight


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 single integer that represents the number of obstructions, and the following lines will have the coordinates of the obstructions, one per line.

Following the final house, a line “0 0 0” will end the file.

For each house, the house will be above the property line (house y > property line y). No obstruction will overlap with the house or property line, e.g. if obstacle y = house y, you are guaranteed the entire range obstacle[x1, x2] does not intersect with house[x1, x2].


For each house, your program should print a line containing the length of the longest continuous segment of the property line from which the entire house can be to a precision of 2 decimal places. If there is no section of the property line where the entire house can be seen, print “No View”.

Sample Input

2 6 6
0 15 0
1 2 1
3 4 1
12 13 1
1 5 5
0 10 0
0 15 1
0 0 0

Sample Output

No View

Link to problem

Solution below . . .

Read more

Company Picnic

Dunk Tank

A highly placed manager at work shows up next to me in the men’s room.

“You going to the company picnic?” he shouts. He’s a boisterous guy.

“Yes!” I reply. “Looking forward to taking a few throws at you in the dunk tank.”

Dunk tank?!” he says. “There’s not going to be any dunk tank.”

“Oh . . . in that case I’m not going.”

“Why Do I Believe What I Believe?”

Thomas Jefferson

My fellow Americans –

About 20 people showed up for Unite the Right last weekend.

That would be a disappointing turnout for a pancake breakfast sponsored by the local softball league, let alone a national rally in Washington, DC.

White supremacy is like the Flat Earth Society, not non-existent, but extremely marginal. It’s a boogeyman to scare people about things that are not real.

A good question to ask is “Why do I believe what I believe?” For example, “Why do I believe in a resurgence of white supremacy when only 20 people in a nation of 300 million can be persuaded to show up at a rally?”

Possible answers include “I saw it on the internet” or “I heard it on TV.” These are perhaps not good answers, in that they open us up to manipulation for political gain, financial gain, and increased readership and viewership.

Thomas Jefferson

Competitive Programming: POJ 2318 – TOYS


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.

Bow with partitions

For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.


The input file contains one or more problems. The first line of a problem consists of six integers, n, m, x1, y1, x2, y2. The number of cardboard partitions is n (0 < n <= 5000) and the number of toys is m (0 < m <= 5000). The coordinates of the upper-left corner and the lower-right corner of the box are (x_1,y_1) and (x_2,y_2), respectively. The following n lines contain two integers per line — U_i, L_i — indicating that the ends of the i-th cardboard partition is at the coordinates (U_i,y_1) and (L_i,y_2). You may assume that the cardboard partitions do not intersect each other and that they are specified in sorted order from left to right. The next m lines contain two integers per line, X_j, Y_j specifying where the j-th toy has landed in the box. The order of the toy locations is random. You may assume that no toy will land exactly on a cardboard partition or outside the boundary of the box. The input is terminated by a line consisting of a single 0.


The output for each problem will be one line for each separate bin in the toy box. For each bin, print its bin number, followed by a colon and one space, followed by the number of toys thrown into that bin. Bins are numbered from 0 (the leftmost bin) to n (the rightmost bin). Separate the output of different problems by a single blank line.

Sample Input

5 6 0 10 60 0
3 1
4 3
6 8
10 10
15 30
1 5
2 1
2 8
5 5
40 10
7 9
4 10 0 10 100 0
20 20
40 40
60 60
80 80
 5 10
15 10
25 10
35 10
45 10
55 10
65 10
75 10
85 10
95 10

Sample Output

0: 2
1: 1
2: 1
3: 1
4: 0
5: 1

0: 2
1: 2
2: 2
3: 2
4: 2


As the example illustrates, toys that fall on the boundary of the box are “in” the box.

Link to problem

Solution below . . .

Read more

Randy Newman at the Hollywood Bowl

Great show . . . he’s 74 years old and doesn’t walk so well from the wings to the piano but he can still play, sing, tell stories, and he has a song catalog that few can equal.

I put the set list into Spotify and included it here.

Boil the Ocean

My first thought is that “Don’t boil the ocean” is not very good advice because boiling the ocean is not a use case that anyone actually has. Why advise people not to do something that no one would do anyway?

My second thought was: why not boil the ocean? Add some onion, garlic, white wine . . . you might get a really nice cioppino! Serves . . . well, I don’t know how many it would serve, but a lot!

Life Gets Better After 50?

About 15 years ago, economists made an unexpected finding: the U-shaped happiness curve. Other things being equal – that is, once conditions such as income, employment, health and marriage are factored out of the equation – life satisfaction declines from our early 20s until we hit our 50s. Then it turns around and rises, right through late adulthood.

So once you factor out all the things that make life miserable, it turns out older people can be just as happy as anyone else!

Sources Say . . .

We can never allow our sources to make allegations, contentious statements or vituperative attacks behind a cloak of anonymity. It weakens our credibility and gives the sources an opportunity to benefit at our expense. It is fundamentally unfair to the other party and thus biased. . . .

If a source wants to make a vituperative attack on an individual, organisation, company or country he or she must speak on the record.

Tom Apple Adventures

Always in the Last Place You Look

Dropbox Loses COO

Competitive Programming: POJ 1905 – Expanding Rods


Expanding rods

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.


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.


For each line of input, output one line with the displacement of the center of the rod in millimeters with 3 digits of precision.

Sample Input

1000 100 0.0001
15000 10 0.00006
10 0 0.001
-1 -1 -1

Sample Output


Link to problem

Solution below . . .

Read more

The Holy Fire is Now the Forrest Fire

It’s wildfire season here in Southern California . . .

The closest fire to us at this time is the Holy Fire, named either for its proximity to the small mountain community of Holy Jim (see map), or because God is purifying us with flame. Jesus returned as a burning bush and inadvertently ignited Trabuco Canyon.

A suspect, Forrest Gordon Clark, has been arrested on suspicion of arson.

Forrest Gordon Clark

He looks normal. The fire has been renamed from the Holy Fire to the Forrest Fire. πŸ™‚

My wife is in the insurance business. Every summer she gets calls from people living in fire zones wanting to buy a homeowners policy.

There’s no concept of guaranteed issue with homeowners insurance like there is with health insurance.

— Does your house have a pre-existing condition?

Yes, it’s on fire.

— OK, your first month’s premium will be $500,000.

More Words and Phrases I’m Sick Unto Death Of: Thought Leader

X-ray glasses

If “thought leader” is a title you can bestow upon yourself, then what is the difference between a thought leader and a crackpot?

I am a thought leader, a proponent of unconventional ideas. You, on the other hand, are a crackpot.

I am a visionary. I have visions. Sometimes I have them when I’m driving and I have to pull over. It’s a real burden . . .

See You in Hell


[See You in Hell is a feature by our guest blogger, Satan — PE]

Greetings from the infernal regions!

Man arrested at New Mexico compound was allegedly training child to commit school shootingsNBC News

Here’s a photo of the gentleman in question, Siraj Ibn Wahhaj:

Siraj Ibn Wahhaj

One of the few black men in America actively involved in his children’s lives. Kudos, sir!

See you in Hell . . .

First Lines

Newest addition to Lit Quizzes. identify the source and author.

Hazel Motes sat at a forward angle on the green plush train seat, looking one minute at the window as if he might want to jump out of it, and the next down the aisle at the other end of the car.

Math Skills of the Average American


My son was home for a visit this past weekend. After a family dinner at the Irvine Spectrum, we found ourselves in a women’s clothing store with a sale going on: 40% Off All Merchandise + An Additional 10% Off.

My son said to me, “Isn’t that just 46 percent off? They probably want it to sound like you’re getting 50 percent off.”

“You can’t underestimate the math skills of the average American,” I said.

Right on queue, a woman said to her husband, “Why don’t they just say 50 percent off?”

“Exactly,” he said.

Was Jim Acosta’s Life in Danger?

It doesn’t look that way to me:

You Are Very Fake News

Click to order!

Fake News t-shirt

Update 5 Aug 2018: Newseum has decided to stop selling these shirts and apologized for selling them in the first place. πŸ™

Fortunately I ordered mine yesterday. πŸ™‚

Thomas Jefferson: Jim Acosta vs. Ernie Pyle

Thomas Jefferson

My fellow Americans –

I see that journalists are now positioning themselves as putting their lives on the line for America.

Some poor fool at CNN was afraid of being murdered when he showed up at a Trump rally and people chanted “CNN sucks!”

He’s not exactly Ernie Pyle, is he?

A CNN reporter at a Trump rally is like a guy wearing a Yankees jersey to a Red Sox game. “You suck” doesn’t mean “I want to murder you.”

I have never heard anyone advocating violence against journalists except other journalists. It’s all they talk about. There’s going to be violence against journalists! Our lives are in jeopardy!

In the event of violence against journalists, no one will happier than journalists, because they will blame it on President Trump.

Meanwhile, in a journalistic spirit of peace and rapprochement, the New York Times has just added a woman to its editorial board who encourages her Twitter followers to “kill all men.”

Thomas Jefferson

“You’re Too Hard on Yourself”

“He has suffered enough” meant if we investigate this matter any further, it will turn out our friends are in it, too. A sufficiency of suffering, in public life, consisted in a loss of face perhaps, or office, or, earlier, in getting caught, or in committing crimes, or having wanted to commit them. And if the real sufferer was the public man in violation of the criminal law, and a sufficiency of suffering lay in his various states of mind, then it was perhaps everyone else who got off too easily. . . .

Intelligent people, caught at anything, denied it. Faced with evidence of having denied it falsely, people said they had not done it and had not lied about it, and didn’t remember it, but if they had done it or lied about it, they would have done it and misspoken themselves about it in an interest so much higher as to alter the nature of doing and lying altogether. It was in the interest of absolutely nobody to get to the bottom of anything whatever. . . . The jig was never up. In every city, at the same time, therapists earned their living by saying “You’re too hard on yourself.”

— Renata Adler, Speedboat