TLE '16 Contest 6 (Mock CCC) S2 - Paper Stapling

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

William takes the first page of the CCC (top image) and turns it over (bottom image). Note the missing corner in the top left of the page, caused by the stapling.

The top computer scientists in Canada have just started the Canadian Computing Cancer (CCC), but Jason and William experience a huge problem. As it turns out, the CCC booklets are so poorly stapled that some words on the top left corner of the page cannot be read. Important pieces of info are cut off due to the stapling, such as the name of the problem's protagonist. The CCC cannot provide a PDF version of the problems because those who start late would have an unfair advantage.

Due to this issue, William measures the endpoints of the staples to be at $2$ ~2~ distinct points $(x_1, y_1)$ ~(x_1, y_1)~ and $(x_2, y_2)$ ~(x_2, y_2)~ where $(0, 0)$ ~(0, 0)~ is at the top left corner of the contest package. The x-coordinate increases infinitely as one moves right, and the y-coordinate increases infinitely as one moves down. In order to start the contest, he folds over the first page and makes a crease in a way that maximizes the amount of legible space on the second page. Jason looks at the page and notices that the missing region of the paper forms a right-angled triangle.

What area of paper is left illegible on William's page?

Input Specification

The first line will contain two space-separated integers $x_1$ ~x_1~ and $y_1$ ~y_1~ $(1 \le x_1, y_1 \le 10^6)$ ~(1 \le x_1, y_1 \le 10^6)~.

The second line will contain two space-separated integers $x_2$ ~x_2~ and $y_2$ ~y_2~ $(1 \le x_2, y_2 \le 10^6)$ ~(1 \le x_2, y_2 \le 10^6)~.

The coordinates are distinct points, i.e., $(x_1, y_1) \ne (x_2, y_2)$ ~(x_1, y_1) \ne (x_2, y_2)~.

For 3 of the 15 points, all coordinates will not exceed $2$ ~2~.

For an additional 3 of the 15 points, $x_1 < x_2$ ~x_1 < x_2~ and $y_1 < y_2$ ~y_1 < y_2~.

Output Specification

Print out the area of paper missing from William's page. An absolute or relative error of $10^{-6}$ ~10^{-6}~ will be considered correct.

Sample Input 1

6 1
1 5

Sample Output 1

21.025000000

Sample Input 2

1 1
3 7

Sample Output 2

42.000000000

Comments

1

aeternalis1 commented on July 22, 2017, 8:20 p.m.

Am I missing something?

I'm fairly certain I've taken all possible staples into account, yet I can't get test cases 3, 4, or 5.

0

davidgu commented on Feb. 21, 2017, 1:54 a.m.

Java outputs large doubles in scientific notation. Will this be accepted by the judge?

0

d commented on Feb. 21, 2017, 1:54 a.m.

Yes.

2

haoda commented on Feb. 20, 2017, 10:49 p.m.

How is sample test case2 even possible?

0

d commented on Feb. 21, 2017, 12:58 a.m.

It is possible that the missing right-angled triangle has vertices $(0,0)$ ~(0,0)~, $(6,0)$ ~(6,0)~ and $(0,14)$ ~(0,14)~. The area of this triangle is $\frac{6*14} 2 = 42$ ~\frac{6*14} 2 = 42~, which is minimal.

0

bobhob314 commented on Feb. 20, 2017, 9:09 p.m.

So it's guaranteed that the missing area is a non-degenerate, right angled triangle?

0

ZQFMGB12 commented on Feb. 20, 2017, 10:18 p.m.

Since coordinates are at least 1, yes.

0

Ken_Shi commented on Feb. 20, 2017, 6:05 p.m.

Am I the only idiot who stuck at the third case first one???