codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1869B.md (3197B)


      1 Source: https://codeforces.com/problemset/problem/1869/B
      2 
      3 B. 2D Traveling
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Piggy lives on an infinite plane with the Cartesian coordinate system on it.
     22 
     23 There are $n$ cities on the plane, numbered from $1$ to $n$, and the first $k$ cities are defined as major cities. The coordinates of the $i$-th city are $(x_i,y_i)$.
     24 
     25 Piggy, as a well-experienced traveller, wants to have a relaxing trip after Zhongkao examination. Currently, he is in city $a$, and he wants to travel to city $b$ by air. You can fly between any two cities, and you can visit several cities in any order while travelling, but the final destination must be city $b$.
     26 
     27 Because of active trade between major cities, it's possible to travel by plane between them for free. Formally, the price of an air ticket $f(i,j)$ between two cities $i$ and $j$ is defined as follows:
     28 
     29 $$ f(i,j)= \begin{cases} 0, & \text{if cities }i \text{ and }j \text{ are both major cities} \\ |x_i-x_j|+|y_i-y_j|, & \text{otherwise} \end{cases} $$
     30 
     31 Piggy doesn't want to save time, but he wants to save money. So you need to tell him the minimum value of the total cost of all air tickets if he can take any number of flights.
     32 
     33 Input
     34 
     35 The first line of input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of test cases follows.
     36 
     37 The first line of each test case contains four integers $n$, $k$, $a$ and $b$ ($2\le n\le 2\cdot 10^5$, $0\le k\le n$, $1\le a,b\le n$, $a\ne b$) — the number of cities, the number of major cities and the numbers of the starting and the ending cities.
     38 
     39 Then $n$ lines follow, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9\le x_i,y_i\le 10^9$) — the coordinates of the $i$-th city. The first $k$ lines describe major cities. It is guaranteed that all coordinates are pairwise distinct.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, print a single integer — the minimum value of the total price of all air tickets.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 6 2 3 5
     55 
     56 0 0
     57 
     58 1 -2
     59 
     60 -2 1
     61 
     62 -1 3
     63 
     64 2 -2
     65 
     66 -3 -3
     67 
     68 2 0 1 2
     69 
     70 -1000000000 -1000000000
     71 
     72 1000000000 1000000000
     73 
     74 7 5 4 2
     75 
     76 154 147
     77 
     78 -154 -147
     79 
     80 123 456
     81 
     82 20 23
     83 
     84 43 20
     85 
     86 998 244
     87 
     88 353 100
     89 
     90 3 1 3 1
     91 
     92 0 10
     93 
     94 1 20
     95 
     96 2 30
     97 
     98 4 3 2 4
     99 
    100 0 0
    101 
    102 -100 100
    103 
    104 -1 -1
    105 
    106 -1 0
    107 ```
    108 
    109 Output
    110 
    111 ```
    112 4
    113 4000000000
    114 0
    115 22
    116 1
    117 ```
    118 
    119 Note
    120 
    121 In the first test case:
    122 
    123  ![](https://espresso.codeforces.com/fa3d31be9cc4a298dcd292e118f7e219528bde35.png) The major cities are marked red. 
    124 
    125 The optimal way to choose the flights is: $3\rightarrow 1 \rightarrow 2 \rightarrow 5$, which will cost $3+0+1=4$. Note that the flight $1\rightarrow 2$ costs $0$, because both city $1$ and $2$ are major cities.
    126 
    127 In the second test case, since there are only $2$ cities, the only way is to take a flight from city $1$ to $2$.
    128 
    129 In the third test case, since city $2$ and $4$ are both major cities, Piggy can directly take a flight from city $2$ to $4$, which costs $0$.
    130 
    131 In the fourth test case, Piggy can choose to take the following flights: $3\rightarrow 2\rightarrow 1$, and the cost is $11+11=22$.