_kiran_iitm | Logout
You have +357! Wow!
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT CODE MY SUBMISSIONS STATUS HACKS ROOM STANDINGS CUSTOM INVOCATION
Codeforces Round 1098 (Div. 2)
D. Sanae, Cross and Color Contest is running
time limit per test: 2 seconds
01:32:47
memory limit per test: 256 megabytes
Contestant
Faith Is for the Transient
People
— Mountain of Faith
Upon the mountain, Sanae gazes at the stars. Faith, for her, is where winds encounter one → Submit?
another and choices diverge, and it is the point where all directions meet. For the glory of the
Holy Cross, let us trace the sign of faith together.
Language: Python 3.13.2
Almost always, if you send a solution
There are n distinct integer points in the plane, where the i -th point is located at (x i , yi ). To on PyPy, it works much faster
color the points, choose two integers k1 and k2 such that each of the four regions divided by Choose
Choose File No file chosen
the lines x = k1 + 0.5 and y = k2 + 0.5 contains at least one point. Each point (x, y) is file:
colored according to the region it lies in: Be careful: there is 50 points penalty for
submission which fails the pretests or
resubmission (except failure on the first test,
Top-left (x ≤ k 1 and y > k 2 ): the point is colored red. denial of judgement or similar verdicts).
Top-right (x > k1 and y > k2 ): the point is colored green. "Passed pretests" submission verdict doesn't
guarantee that the solution is absolutely
Bottom-left (x ≤ k1 and y ≤ k2 ): the point is colored blue. correct and it will pass system tests.
Bottom-right (x > k1 and y ≤ k2 ): the point is colored yellow.
Submit
→ Score table
Score
Problem A 418
Problem B 627
Problem C1 1254
Problem C2 836
Problem D 2090
Problem E1 1672
Problem E2 1254
A valid coloring of the third test case, where k1 = 4 and k2 = 5 . Problem F 2926
Find the number of distinct colorings, where two colorings are considered distinct if and only if
Successful hack 100
there exists at least one point colored differently, regardless of the choice of k1 and k2 .
Unsuccessful hack -50
Input Unsuccessful submission -50
Each test contains multiple test cases. The first line contains the number of test cases t (
4
Resubmission -50
1 ≤ t ≤ 10 ). The description of the test cases follows. * If you solve problem on 00:41 from the first attempt
The first line of each test case contains an integer n (4
6
≤ n ≤ 2 ⋅ 10 ).
The following n lines each contain two integers x i , yi (1 ≤ x i , yi ≤ n ), representing the
coordinates of the i -th point.
It is guaranteed that the points are pairwise distinct in each test case.
6
It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10 .
Output
For each test case, output the number of distinct colorings.
Example
input Copy
5
4
1 1
2 2
3 3
4 4
4
1 4
4 1
1 1
4 4
8
7 2
5 7
2 7
1 3
6 7
3 6
7 5
1 6
8
6 1
3 6
1 4
1 1
4 2
5 5
3 4
4 1
6
5 5
5 4
3 5
1 5
5 3
2 2
output Copy
0
1
12
8
4
Note
In the first test case, no valid cross exists.
In the second test case, choosing x = y = 2 yields a valid coloring. It can be proved that this
coloring is unique.
In the third test case, a valid coloring is shown in the legend.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/16/2026 20:46:49UTC+5.5 (l1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by