Codeforces Round 767 (Div. 1)

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.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1628 Codeforces Round 767 (Div. 1) FINISHED False 7200 94404263 Jan. 22, 2022, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 90 ) F Spaceship Crisis Management PROGRAMMING binary search data structures geometry sortings

B'NASA (Norwegian Astronaut Stuff Association) is developing a new steering system for spaceships. But in its current state, it wouldn 't be very safe if the spaceship would end up in a bunch of space junk. To make the steering system safe, they need to answer the following: Given the target position t = (0, 0) , a set of n pieces of space junk l described by line segments l_i = ((a_{ix}, a_{iy}), (b_{ix}, b_{iy})) , and a starting position s = (s_x, s_y) , is there a direction such that floating in that direction from the starting position would lead to the target position? When the spaceship hits a piece of space junk, what happens depends on the absolute difference in angle between the floating direction and the line segment, theta : You are only given the set of pieces of space junk once, and the target position is always (0, 0) , but there are q queries, each with a starting position s_j = (s_{jx}, s_{jy}) . Answer the above question for each query. The first line contains the the integer n ( 1 <= n <= 1500 ). Then follows n lines, the i -th of which containing the 4 integers a_{ix} , a_{iy} , b_{ix} , and b_{iy} ( |a_{ix}|, |a_{iy}|, |b_{ix}|, |b_{iy}| <= 1000 ). Then follows a line containing the integer q ( 1 <= q <= 1000 ). Then follows q lines, the j -th of which containing the 2 integers s_{jx} and s_{jy} ( |s_{jx}|, |s_{jy}| <= 1000 ). It is guaranteed that none of the segments in l cross or touch, that t is not on any segment in l , that s_j is not on any segment in l , and that s neq t . For each query s_j print an answer. If there exists a direction such that floating from s_j in that direction, possibly sliding along some pieces of space junk, leads to t , print "YES". Otherwise, print "NO" (case insensitive). The blue cross represents the targe'...

Tutorials

99276

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
143706221 rainboy F Jan. 22, 2022, 5:48 p.m. OK GNU C11 TESTS 26 7254 204800
143702198 ecnerwala F Jan. 22, 2022, 5:25 p.m. OK GNU C++17 (64) TESTS 26 2027 307200
143703628 Benq F Jan. 22, 2022, 5:30 p.m. OK GNU C++17 (64) TESTS 26 2901 716800
143702221 SpyCheese F Jan. 22, 2022, 5:25 p.m. OK GNU C++17 (64) TESTS 26 2995 1228800
143705808 rainboy F Jan. 22, 2022, 5:44 p.m. OK GNU C++17 (64) TESTS 26 5194 102400
143703556 Petr F Jan. 22, 2022, 5:30 p.m. OK GNU C++17 (64) TESTS 26 5491 614400
143704137 tourist F Jan. 22, 2022, 5:33 p.m. OK GNU C++17 (64) TESTS 26 6582 1638400
143717594 brunovsky F Jan. 22, 2022, 8:29 p.m. OK GNU C++20 (64) TESTS 26 187 716800

remove filters

Back to search problems