1 5
-9 2
0 0
4 2
-2 5
-4 6
0 4
-6 7
2 3

Answer: 0

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;

I've got a wrong answer on test 15.
By the way... in order to satisfy condition #4 we need to test each "good" point with each "good" point? won't it be too much iterations for n=10000?
P.S. "good" point is the point that satisfy the current arc?

shit!= =

Does anybody know?