The new time limit for the problem id 4 seconds. With old time limit 5 seconds bruteforce solutions could pass all tests.

Please decrease time limit again. Trivial brute force can pass all tests:
http://acm.timus.ru/getsubmit.aspx/6872297.cpp

I think time limit should be decreased down to 1 second. It is not hardest problem otherwise.
My AVX solution w/o custom input/output can pass all the tests too. http://acm.timus.ru/getsubmit.aspx/6871223.cpp
Another way to make this problem interesting is to change N from 10000 to 100000.

AVX? :) if solution requires manual vectorization to avoid TL - it is still hard problem,
but trivial (double precision) arithmetic is enough here for now.

Edited by author 08.06.2016 04:43

IMO time limit should be 2 (or 3) seconds - it breaks brute force, at least for now,
but still allow(?) good java solutions (best - 1.7 seconds).

Simple arithmetic gives TLE 9. BTW Fortune's algorithm also implies just only trivial arithmetic (i.e. +-*/), do you mean this?

No, I mean absolutely straightforward O(N*M) algorithm, 20 lines of c/++

So, I reached 1.7 seconds It is not brute force now (since there are several non-trivial optimizations), but it is still O(N*M) algorithm... It should be 1.5-2X faster when AVX512 is available.

AVX (256 bit, 4 dobule) is not faster then SSE (128 bit, 2 double) on the judging system, though. Because of bus width, I think.

       gcc  msvc
1xD:   TL9 3.260
2xD: 1.981 2.308
4xD: 1.575 1.482

Edited by author 10.06.2016 12:55

I really want to see your solution! Can we trade it for top3?

Edited by author 10.06.2016 22:27

Just understand what is "top3" - thank you - no, I like problem solving :)

Edited by author 11.06.2016 06:44

That means problem 1548.
Anyways I will to solve this problem using Voronoi. But now I just especially interested in manual vectorization technique. And SSE/AVX/AVX512 solution is just a "reference point" for "right" solution via Fortune's algorithm.

Yep, I understood.
Please share your email. I don't think that my solution will help you, it is based on very specific optimizations.

See profile...

How to improve SSE solution in such a way, that it became 2.5x faster? Very interesting optimizations should be here.

Edited by author 13.06.2016 01:39

New time limit is set to 2 sec. Thanks for reporting a problem.

It seems that solutions of other problems may have benefit from new hardware too. Maybe it make sense to rejudge a couple of tens of hardest problems (at least 100-200 top solutions).