Clarifications added to the problem statement regarding river basin definition, river intersection restrictions and input precision.

Tests that were invalid according to the clarifications have been fixed or replaced. Tests 9 and 13 contained overlapping segments making the river flow the same path back and forth; the tests have been replaced with new tests. Tests 15, 16, 18, 19 contained rivers with self-intersections; the tests have been corrected. Test 23 contained a river with a mouth lying on the segment of the other river and didn’t count as tributary; the test has been corrected, this situation is no longer allowed in the tests.

New tests have been added. In particular, tests with more than 2 rivers in a basin have been introduced.

All solutions have been rejudged. 106 authors lost, and 12 other authors gained the solved status for the problem.

Edited by author 18.08.2024 01:04

Two segments of rivers (a, b) and (c, d) intersects iff a == c or a == d or b == c or b == d

two rivers are considered to be connected iff they share at least one vertex (no matter inner vertex or end vertex)

example 1:
2
2
-1 0
1 0
2
0 1
0 -1
not connected, because their intersection (0, 0) is not a vertex of river 1 or river 2

example 2:
2
2
-1 0
1 0
3
0 1
0 0
0 -1
not connected, because (0, 0) is not a vertex of River 1

example 3:
2
3
0 1
0 0
0 -1
3
-1 0
0 0
1 0
connected, because (0, 0) appears on both rivers

Can somebody help me with this test?

I think there is some small bug in my program or in the statement understanding, but I can't find it...
An appropriate test would help me a lot.

//
below, when speaking about broken lines, for any line I divide it's points into endpoints (first and last) and inner points (the rest)
//

I had the following 4 questions when solving this problem:

1. Is "tributarity" transitive? I.e. when calculating basin area, do we only consider the river and it's tributaries, or do we also look at tributaries' tributaries, and tributaries of those tributaries etc?

2. Is it assumed that points in the river are ordered from head to mouth (or from head to entry-to-parent-river)?

3. Is it true that a river A is a tributary of river B if and only if one of endpoints of A is an inner point (not endpoint!) of B?

4. Can an inner vertex be a turning point and an entry point  of a tributary flow at the same time (or tributaries only enter in points which lie on some straight part of the broken line - like in problem samples)?

I did the following assumptions and got AC, so either they are right or there's no testdata to distinguish:

1. Yes, we include all the hierarchy
2. No, any endpoint may be an entry to a "parent" river. But not both - one of 2 endpoints is always head (as problem statement says)
 NOTE: this is only my (maybe false) assumption that complicates things just a bit, and doesn't contradict the opposite assumption, but covers it instead.
3. Yes.
4. Yes. All inner points can be subflows' entry points.

P.S. In fact, question 2 is almost unnecesary because problem statement says: "Every river is shown as a broken line, which begins with a river head and ends either at the point where the river flows into another one, or on the river mouth". The problematic word here is "shown". Is it equal to "given in input file?", i.e. does this order correspond to input data?

Edited by author 06.02.2006 02:44

Edited by author 06.02.2006 02:46

What is numbeblem or this problem?