oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

explosion Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

explosion.html

Problem Description

Rar the Cat is part-timing as an urban planner. As part of his new career, he has to model the effects of potential explosions in his city.

Rar's city can be modelled as a 2D grid, with N buildings, where the ith building is located at a coordinate (Xi, Yi).

In his simulation, an explosion occurs at the point (A, B), and the explosion produces a blastwave that spreads in a diamond shape, as shown below.

Help Rar determine the order in which the buildings will be hit by the expanding blastwave. If two buildings are hit at the same time, output the one with the lowest ID first.

Input

The first line of input will contain three integers, N, A and B. The next N lines of input will contain two integers each, with the ith line containing integers Xi and Yi.

Output

Output a single line containing N integers, indicating the order in which the buildings will be hit. The IDs should be 1-indexed.

Limits

Subtask 1 (25%): 1 ≤ N ≤ 2 000. -1 000 ≤ Xi, Yi ≤ 1 000.

Subtask 2 (33%): 1 ≤ N ≤ 500 000. -1 000 ≤ Xi, Yi ≤ 1 000.

Subtask 3 (42%): 1 ≤ N ≤ 500 000. -109 ≤ Xi, Yi ≤ 109

Subtask 4 (0%): Sample Testcases

Sample Testcase 1

Input

4 0 0
0 0
2 0
1 1
1 0

Output

1 4 2 3

Sample Testcase 2

Input

5 2 3
5 -1
-2 -3
4 5
2 1
0 0

Output

4 3 5 1 2

explosion.png

Tags

Sorting

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
125221s64MBMinimum
233421s64MBMinimum
342621s64MBMinimum
4021s64MBMinimum

Judge Compile Command

g++-8 ans.cpp -o explosion -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.