Solutions are presented as using the least memory and the fastest execution time. It also takes the top
10 most recent solutions from each language. If you want to limit to a specific index, click the
"Solved" button and go to that problem.
Problems
Two irrigation cooperatives share the same fertile valley. The first cooperative maintains pumps scattered across the fields; the second supervises reservoirs on the surrounding hills. Whenever both cooperatives decide to lay a pair of new pipes, the pipes must intersect — at such an intersection they can install a joint valve. Pipes always follow a straight line segment between a pair of distinct pumps or a pair of distinct reservoirs. Two pipes intersect if they share at least one common point (touching and overlapping pipes are considered intersecting). You are given the exact coordinates of every pump and every reservoir on a Cartesian plane. For each planning scenario, determine whether the first cooperative can pick two distinct pumps and the second cooperative can pick two distinct reservoirs so that the two straight pipes intersect. If this is possible, report the indices of those pumps and reservoirs; otherwise declare that the project cannot be realized. The first line contains an integer (t) ((1 \le t \le 10^5)) — the number of planning scenarios. For each planning scenario: The first line contains an integer (n) ((2 \le n \le 10^5)) — the number of pumps managed by the first cooperative. Each of the next (n) lines contains two integers (x_i) and (y_i) ((|x_i|, |y_i| \le 10^9)) — the Cartesian coordinates of pump (i). The pump locations are distinct. The next line contains an integer (m) ((2 \le m \le 10^5)) — the number of reservoirs managed by the second cooperative. Each of the next (m) lines contains two integers (u_j) and (v_j) ((|u_j|, |v_j| \le 10^9)) — the Cartesian coordinates of reservoir (j). The reservoir locations are distinct. No pump shares its location with any reservoir. It is guaranteed that the sum of (n) over all planning scenarios does not exceed (2 \cdot 10^5) and the sum of (m) over all planning scenarios does not exceed (2 \cdot 10^5). For eac |
Tutorials
Submissions
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|
353850223 |
Kevin114514 jiangly jqdai0815 |
I |
Dec. 17, 2025, 12:49 p.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
169 |
484 |
32972800 |
|
|
|
353929500 |
Qwerty1232 |
I |
Dec. 18, 2025, 6 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
169 |
1156 |
53862400 |
|
|
|
353928649 |
Qwerty1232 |
I |
Dec. 18, 2025, 5:49 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
169 |
1218 |
53760000 |
|
|
|
353928359 |
Qwerty1232 |
I |
Dec. 18, 2025, 5:46 a.m. |
OK |
C++23 (GCC 14-64, msys2) |
TESTS |
169 |
1593 |
54374400 |
|
|
remove filters
Back to search problems