Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.
ContestId |
Name |
Phase |
Frozen |
Duration (Seconds) |
Relative Time |
Start Time |
|---|---|---|---|---|---|---|
| 645 | CROC 2016 - Elimination Round | FINISHED | False | 7200 | 318086723 | March 18, 2016, 4:35 p.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 128 ) | G | Armistice Area Apportionment | PROGRAMMING | binary search geometry | 2600 |
After a drawn-out mooclear arms race, Farmer John and the Mischievous Mess Makers have finally agreed to establish peace. They plan to divide the territory of Bovinia with a line passing through at least two of the n outposts scattered throughout the land. These outposts, remnants of the conflict, are located at the points ( x 1 , y 1 ), ( x 2 , y 2 ), ..., ( x n , y n ) . In order to find the optimal dividing line, Farmer John and Elsie have plotted a map of Bovinia on the coordinate plane. Farmer John's farm and the Mischievous Mess Makers' base are located at the points P = ( a , 0) and Q = ( - a , 0) , respectively. Because they seek a lasting peace, Farmer John and Elsie would like to minimize the maximum difference between the distances from any point on the line to P and Q . Formally, define the difference of a line relative to two points P and Q as the smallest real number d so that for all points X on line , | PX - QX | ≤ d . (It is guaranteed that d exists and is unique.) They wish to find the line passing through two distinct outposts ( x i , y i ) and ( x j , y j ) such that the difference of relative to P and Q is minimized. The first line of the input contains two integers n and a ( 2 ≤ n ≤ 100 000 , 1 ≤ a ≤ 10 000 ) — the number of outposts and the coordinates of the farm and the base, respectively. The following n lines describe the locations of the outposts as pairs of integers ( x i , y i ) ( | x i |, | y i | ≤ 10 000 ). These points are distinct from each other as well as from P and Q . Print a single real number—the difference of the optimal dividing line. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6 . Namely: let's assume that your answer is a , and the answer of the jury is b . The checker program will consider your answer correct, if . In the first sample case, the only possible line is y = x - 1 . It can be shown that the point X which maximizes | PX - QX | is (13, 12) , with , whic |
| Editorial for CROC 2016 Elimination Round |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 36267900 | jzqjzq | G | March 14, 2018, 7:46 a.m. | OK | GNU C++ | TESTS | 100 | 78 | 3276800 | 2600 | |
| 36266898 | yukuai26 | G | March 14, 2018, 6:54 a.m. | OK | GNU C++ | TESTS | 100 | 124 | 7065600 | 2600 | |
| 36273283 | yasugongshang | G | March 14, 2018, 11:36 a.m. | OK | GNU C++ | TESTS | 100 | 202 | 11366400 | 2600 | |
| 36325698 | zhan8855 | G | March 16, 2018, 12:37 p.m. | OK | GNU C++ | TESTS | 100 | 312 | 7065600 | 2600 | |
| 22897586 | ELNUR.ktl | G | Dec. 12, 2016, 4:19 a.m. | OK | GNU C++ | TESTS | 100 | 342 | 5222400 | 2600 | |
| 16902453 | 130705009 | G | March 24, 2016, 7:59 a.m. | OK | GNU C++ | TESTS | 100 | 343 | 7475200 | 2600 | |
| 28471492 | progg_admin | G | July 12, 2017, 11:04 a.m. | OK | GNU C++ | TESTS | 100 | 343 | 8396800 | 2600 | |
| 16801144 | RNS3 | G | March 19, 2016, 4:41 a.m. | OK | GNU C++ | TESTS | 100 | 358 | 5222400 | 2600 | |
| 27771112 | jiyutian | G | June 14, 2017, 9:15 a.m. | OK | GNU C++ | TESTS | 100 | 358 | 6348800 | 2600 | |
| 17186108 | Philipsweng | G | April 6, 2016, 12:10 p.m. | OK | GNU C++ | TESTS | 100 | 374 | 9011200 | 2600 | |
| 36265811 | wzporz | G | March 14, 2018, 5:48 a.m. | OK | GNU C++11 | TESTS | 100 | 156 | 5324800 | 2600 | |
| 36265741 | wzporz | G | March 14, 2018, 5:45 a.m. | OK | GNU C++11 | TESTS | 100 | 171 | 5324800 | 2600 | |
| 36266668 | emoairx | G | March 14, 2018, 6:41 a.m. | OK | GNU C++11 | TESTS | 100 | 218 | 6758400 | 2600 | |
| 52752967 | luogu_bot1 | G | April 14, 2019, 3:07 p.m. | OK | GNU C++11 | TESTS | 100 | 249 | 6144000 | 2600 | |
| 52752943 | cjrsacred | G | April 14, 2019, 3:06 p.m. | OK | GNU C++11 | TESTS | 100 | 249 | 6144000 | 2600 | |
| 52889147 | was_n | G | April 17, 2019, 7 a.m. | OK | GNU C++11 | TESTS | 100 | 249 | 12800000 | 2600 | |
| 37877365 | AmberFrame | G | May 4, 2018, 7:47 a.m. | OK | GNU C++11 | TESTS | 100 | 280 | 13721600 | 2600 | |
| 16873995 | ershov.stanislav | G | March 22, 2016, 4:06 p.m. | OK | GNU C++11 | TESTS | 100 | 296 | 12902400 | 2600 | |
| 17007597 | uikos | G | March 28, 2016, 6:48 p.m. | OK | GNU C++11 | TESTS | 100 | 342 | 12288000 | 2600 | |
| 27471330 | 754986421653 | G | May 31, 2017, 4:43 p.m. | OK | GNU C++11 | TESTS | 100 | 343 | 5222400 | 2600 | |
| 30990533 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 11:27 a.m. | OK | GNU C++14 | TESTS | 100 | 46 | 1740800 | 2600 | |
| 40984773 | ReaLNero1 | G | July 30, 2018, 7:34 p.m. | OK | GNU C++14 | TESTS | 100 | 62 | 1740800 | 2600 | |
| 30989890 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:51 a.m. | OK | GNU C++14 | TESTS | 100 | 171 | 2867200 | 2600 | |
| 39236706 | XingGeRuCi | G | June 14, 2018, 8:49 a.m. | OK | GNU C++14 | TESTS | 100 | 249 | 9728000 | 2600 | |
| 52635975 | Shedneryan | G | April 12, 2019, 10:03 a.m. | OK | GNU C++14 | TESTS | 100 | 264 | 11673600 | 2600 | |
| 52586933 | cz_xuyixuan | G | April 11, 2019, 1:14 a.m. | OK | GNU C++14 | TESTS | 100 | 280 | 11980800 | 2600 | |
| 32455384 | NiroBC | G | Nov. 19, 2017, 11:40 a.m. | OK | GNU C++14 | TESTS | 100 | 546 | 5529600 | 2600 | |
| 53100220 | vjudge3 | G | April 21, 2019, 3:58 p.m. | OK | GNU C++14 | TESTS | 100 | 655 | 8704000 | 2600 | |
| 36267789 | zhanglexing | G | March 14, 2018, 7:40 a.m. | OK | GNU C++14 | TESTS | 100 | 748 | 5222400 | 2600 | |
| 37794003 | kut_kjb1994 | G | May 1, 2018, 9:39 a.m. | OK | GNU C++14 | TESTS | 100 | 811 | 11980800 | 2600 | |
| 64012695 | hjk1030 | G | Nov. 1, 2019, 3:15 p.m. | OK | GNU C++17 | TESTS | 100 | 327 | 9523200 | 2600 | |
| 63094565 | how_to_become_purple | G | Oct. 21, 2019, 7:55 p.m. | OK | GNU C++17 | TESTS | 100 | 654 | 8908800 | 2600 | |
| 52643404 | jah_melon | G | April 12, 2019, 1:26 p.m. | OK | GNU C++17 | TESTS | 100 | 873 | 2457600 | 2600 | |
| 53385523 | jah_melon | G | April 27, 2019, 3:13 a.m. | OK | GNU C++17 | TESTS | 100 | 1045 | 10854400 | 2600 | |
| 68564145 | xiaowuc1 | G | Jan. 10, 2020, 8:09 p.m. | OK | GNU C++17 | TESTS | 100 | 1497 | 8499200 | 2600 | |
| 18049825 | kafy83 | G | May 24, 2016, 2:53 a.m. | OK | Java 8 | TESTS | 100 | 685 | 42086400 | 2600 | |
| 16795347 | Petr | G | March 18, 2016, 6:33 p.m. | OK | Java 8 | TESTS | 100 | 701 | 15462400 | 2600 | |
| 16954657 | rishus23 | G | March 26, 2016, 11:07 a.m. | OK | Java 8 | TESTS | 100 | 717 | 37990400 | 2600 | |
| 18049777 | kafy83 | G | May 24, 2016, 2:44 a.m. | OK | Java 8 | TESTS | 100 | 826 | 51404800 | 2600 | |
| 30990582 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 11:30 a.m. | OK | MS C++ | TESTS | 100 | 31 | 1945600 | 2600 | |
| 30990618 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 11:32 a.m. | OK | MS C++ | TESTS | 100 | 46 | 1945600 | 2600 | |
| 30990454 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 11:23 a.m. | OK | MS C++ | TESTS | 100 | 109 | 2764800 | 2600 | |
| 30990418 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 11:21 a.m. | OK | MS C++ | TESTS | 100 | 109 | 2764800 | 2600 | |
| 30989843 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:49 a.m. | OK | MS C++ | TESTS | 100 | 109 | 2969600 | 2600 | |
| 30990025 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:58 a.m. | OK | MS C++ | TESTS | 100 | 124 | 2764800 | 2600 | |
| 30989878 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:51 a.m. | OK | MS C++ | TESTS | 100 | 124 | 2969600 | 2600 | |
| 30989835 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:49 a.m. | OK | MS C++ | TESTS | 100 | 218 | 2969600 | 2600 | |
| 30989588 | Los_Angelos_Laycurse | G | Oct. 4, 2017, 10:36 a.m. | OK | MS C++ | TESTS | 100 | 342 | 2969600 | 2600 | |
| 16834091 | Los_Angelos_Laycurse | G | March 20, 2016, 8:12 a.m. | OK | MS C++ | TESTS | 100 | 889 | 5017600 | 2600 |
Back to search problems