Mooball Teams III
다이아몬드 IV의견: 0
Farmer John has \(N\) cows on his farm (\(2 \leq N \leq 2\cdot 10^5\)), conveniently
numbered \(1 \dots N\). Cow \(i\) is located at integer coordinates \((x_i, y_i)\)
(\(1\le x_i,y_i\le N\)). Farmer John wants to pick two teams for a game of
mooball!
One of the teams will be the "red" team; the other team will be the "blue" team.
There are only a few requirements for the teams. Neither team can be empty, and
each of the \(N\) cows must be on at most one team (possibly neither). The only
other requirement is due to a unique feature of mooball: an infinitely long net,
which must be placed as either a horizontal or vertical line in the plane at a
non-integer coordinate, such as \(x = 0.5\). FJ must pick teams so that it is
possible to separate the teams by a net. The cows are unwilling to move to make
this true.
Help a farmer out! Compute for Farmer John the number of ways to pick a red team
and a blue team satisfying the above requirements, modulo \(10^9+7\).
Problem credits: Dhruv Rohatgi
SCORING
- Input 5: \(N\le 10\)
- Inputs 6-9: \(N\le 200\)
- Inputs 10-13: \(N\le 3000\)
- Inputs 14-24: No additional constraints.
Problem credits: Dhruv Rohatgi
The first line of input contains a single integer \(N.\)
The next \(N\) lines of input each contain two space-separated integers \(x_i\) and
\(y_i\). It is guaranteed that the \(x_i\) form a permutation of \(1\dots N\), and
same for the \(y_i\).
A single integer denoting the number of ways to pick a red team and a blue team
satisfying the above requirements, modulo \(10^9+7\).
2
1 2
2 12We can either choose the red team to be cow 1 and the blue team to be cow 2, or
the other way around. In either case, we can separate the two teams by a net
(for example, \(x=1.5\)).
3
1 1
2 2
3 310Here are all ten possible ways to place the cows on teams; the \(i\)th character
denotes the team of the \(i\)th cow, or . if the \(i\)th cow is not on a team.
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR
3
1 1
2 3
3 212Here are all twelve possible ways to place the cows on teams:
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR
40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40441563023Make sure to output the answer modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Platinum
평가 및 의견
Mooball Teams III
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mooball Teams III