引き続き、C++でB問題を解いていきます。
ABC B056 – NarrowRectanglesEasy
問題
シカのAtCoDeerくんは縦の長さ1、横の長さWの形をした長方形が二つ机に置いてあるのを見つけました。 机を二次元平面とみなすと、以下の図のように、一つ目の長方形は 縦は[0,1]の範囲を、横は[a,a+W]の範囲を占めており、二つ目の長方形は縦は[1,2]の範囲を、横は[b,b+W]の範囲を占めています。
自分の回答
#include <bits/stdc++.h>
using namespace std;
int main () {
int W, a, b;
cin >> W >> a >> b;
int d = abs(a - b) - W;
if(d > 0){
cout << abs(a - b) - W << endl;
}else{
cout << "0" << endl;
}
}二枚の板の距離dはb-(a+W)もしくはa-(b+W)なので、絶対値を使うとabs(a – b) – Wと表すことができます。また、dの値が0以下の時は、最初から板がくっついているということなので、0を出力します。
ABC B057 – Checkpoints
問題
xy平面があり、その上にN人の学生がいて、M個のチェックポイントがあります。
i番目の学生がいる座標は(ai,bi)(1≦i≦N)であり、番号jのチェックポイントの座標は(cj,dj)(1≦j≦M)です。
これから合図があり、各学生はマンハッタン距離で一番近いチェックポイントに集合しなければなりません。
2つの地点(x1,y1)と(x2,y2)間のマンハッタン距離は|x1−x2|+|y1−y2|で表されます。
ここで、|x|はxの絶対値を表します。
ただし、一番近いチェックポイントが複数ある場合には、番号が最も小さいチェックポイントに移動することとします。
合図の後に、各学生がどのチェックポイントに移動するかを求めてください。
自分の回答
#include <bits/stdc++.h>
using namespace std;
int main () {
int n, m;
cin >> n >> m;
int a[n], b[n], c[m], d[m];
for(int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
for(int i = 0; i < m; i++){
cin >> c[i] >> d[i];
}
for(int i = 0; i < n; i++){
int number;
int min_dis = 1e9;
for(int j = 0; j < m; j++){
int dis = abs(a[i]- c[j]) + abs(b[i]- d[j]);
if(dis < min_dis){
min_dis = dis;
number = j + 1;
}
}
cout << number << endl;
}
}マンハッタン距離を使う問題はよく出ますね。
マンハッタン距離を求めて、距離が最小値の時の番号(number)を出力すればいいですね。
