Test:
12
A
B
C
D
E
F
G
H
I
J
K
L
12
A HIT B IN HEAD
A REVIVE B
C HIT D IN HEAD
C REVIVE D
D HIT E IN HEAD
D REVIVE E
F HIT G IN HEAD
F REVIVE G
G HIT H IN HEAD
G REVIVE H
I HIT J IN HEAD
I REVIVE J

Answer:
CORRECT
A B I J
C D E K
F G H L

There are a lot of mistakes in russian statement. I don't think, that is makes sense to write all of them - just read the english statement.

Input:
100 100
0 10
10 10
0 0
19 11
1
10 10
20 10
20 20

Output:
-1

Please give me tests!

Input:
6
0 0
1 1
1 0
2 1
2 0
3 0
7
1 2 12
1 3 2
2 4 10
3 4 10
3 5 10
4 6 1
5 6 13

Output:
11
1 2 9
1 3 2
2 4 9
4 3 8
3 5 10
4 6 1
5 6 10

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.