Hey admins, I've sent a couple of tests to timus_support@acm.timus.ru that my AC solution was struggling with. Please validate if they can be added to the system.

Input:
0 0 0
0 0 1
0 1 0
0 1 -1

Please, tell me the volume of the smaller part of the cone in sample.

Edited by author 07.11.2007 18:23

100 100 100
100 100 100
?

200 100 100
100 50 50
?

i hate this problem

Hi!

I believe test #3 is invalid - there is no way to get from floor 1 to floor N.

Can you please check?

Thank you!

In Soviet times, several gas pipelines were sometimes built from A to B.

Edited by author 19.05.2026 21:32

Input:
2
0 0 1
0 1 0

Output:
2

My algorithm is as follows: I consider planes that cut the sphere in half - they are determined by two points in the input and the center of the sphere. I split the input points in three sets according to this plane - points "above" the plane (say N1 points), points "under" the plane (say N2 points) and points in the plane (all of them being on one circle). Obviously at this moment these points on this circle are not visible since they aren't on the open emisphere, so I try to move this emisphere just a little to make the maximum number of points visible. To handle this, I find the maximum number of points P on some semi-circle. So I conclude that the maximum number of visible points using this plane is the maximum between N1+P and N2+P.

Can you give me a case for which this algorithm is not correct? I get WA on test-case 7. Thanks.

This problem has a more difficult version.
on the acmp.ru website
problem 2142 (values increased)
problem 2249 (tests increased and more difficult tests)

You can solve the problem without using floating point calculations. in32 is enough for everything.

You also needn't to implement BSTrees or Segment trees here. Using ordered sets is enough.

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef __gnu_pbds::tree<
  Point,
  __gnu_pbds::null_type,
  std::less_equal<>,
  __gnu_pbds::rb_tree_tag,
  __gnu_pbds::tree_order_statistics_node_update> ordered_set_less;

typedef __gnu_pbds::tree<
  Point,
  __gnu_pbds::null_type,
  std::greater_equal<>,
  __gnu_pbds::rb_tree_tag,
  __gnu_pbds::tree_order_statistics_node_update> ordered_set_greater;

Input:
1 2
-2 2 0 0 2 2
-1 10
1 10

Output:
0

Why there is so large discussion about easy problems and so few about interesting ones?

FE, let's talk about floating point arifmetics. Did you maid eps (very small 'soft' constant) to 'soft' your calcualtions? What value of your constant? I made it 1e-12 - it vas too small, even 1e-8 was too hard. But with 1e-6 everything was O'Key.

I got WA on test22 for a long time...
what is test22?

if anyone know,please email zhouerjin@gmail.com

It appears you are not handling multiple identical circles correctly.

131071 65536
0 1 0 1 0 1 ... 0 1 0 1 0
answer: 65535 (long time)
131071 65535
0 1 0 1 0 1 ... 0 1 0 1 0
answer: 65536 (long time)
432 234
0 1 0 1 0 1 ... 0 1 0 1
answer: 198

I've got AC with program that returns 01 for input 01.

The test data for this problem has been reworked. New tricky tests have been added. At the same time the majority of the old tests have been removed.

From now on, the total number of tests in this problem is limited to 20 tests. It means if new good tests are discovered, they couldn’t be simply added but should replace some of the old ones.

If you’re stuck, don’t spend time on figuring out the test data and hyperoptimizing, because the test could be replaced with a similar one any time. Instead, detect that your heuristics fail and launch another one in this case. There is no universal test in the test data that makes all the heuristics fail at the same time.

All solutions have been rejudged. Only a few authors still have AC after the rejudge. Because of test removal some of the previously rejected solutions got accepted.

Edited by author 03.05.2026 22:50