Zenn
👌

ARC 051 | A - 塗り絵

2020/11/14に公開
#
競プロ
#
座標
#
図形
tech

問題

https://atcoder.jp/contests/arc051/tasks/arc051_opioppppppppppppppppppppioa

考えたこと

円が赤に、長方形が青に、重なる部分は紫になる。

赤が存在しないとうことは、以下のように円を長方形が覆っていた場合になる。

この場合、以下の緑の4点が長方形の内側にあるかどうか判定すればいい。

青が存在しないということは、以下のように長方形を円が覆っていた場合になる。

この場合は、以下の緑の4点と円の中心との距離がr以下になっているかどうか判定すればいい。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// (x1, y1)と(x2, y2)の距離
ld distance(ld x1, ld y1, ld x2, ld y2) {
  return pow((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2), 0.5);
}

// (cx, cy): 円の座標, r: 円の半径, (x,y): 対象の座標
bool inCircle(ld cx, ld cy, ld r, ld x, ld y) {
  return distance(cx, cy, x, y) <= r;
}

// (x,y)が長方形(rx1, ry1, rx2, ry2)の中に入っているか
bool inRectangle(ld rx1, ld ry1, ld rx2, ld ry2, ld x, ld y) {
  if (rx2 < rx1) {
    swap(rx1, rx2);
  }
  if (ry2 < ry1) {
    swap(ry1, ry2);
  }
  return rx1 <= x && x <= rx2 && ry1 <= y && y <= ry2;
}

// 円が長方形の中にあるか
bool circleInRectangle(ld cx, ld cy, ld r, ld rx1, ld ry1, ld rx2, ld ry2) {
  vector<ll> x = {1, 0, -1, 0};
  vector<ll> y = {0, 1, 0, -1};
  for (int i = 0; i < x.size(); i++) {
    ld nx = cx + x[i] * r;
    ld ny = cy + y[i] * r;
    if (!inRectangle(rx1, ry1, rx2, ry2, nx, ny)) {
      return false;
    }
  }
  return true;
}

// 長方形が円の中にあるか
bool rectangleInCircle(ld rx1, ld ry1, ld rx2, ld ry2, ld cx, ld cy, ld r) {
  vector<ld> x = {rx1, rx2, rx1, rx2};
  vector<ld> y = {ry1, ry1, ry2, ry2};
  for (int i = 0; i < x.size(); i++) {
    if (!inCircle(cx, cy, r, x[i], y[i])) {
      return false;
    }
  }
  return true;
}

int main() {
  ld cx, cy, r;
  cin >> cx >> cy >> r;
  ld rx1, ry1, rx2, ry2;
  cin >> rx1 >> ry1 >> rx2 >> ry2;
  if (circleInRectangle(cx, cy, r, rx1, ry1, rx2, ry2)) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
  if (rectangleInCircle(rx1, ry1, rx2, ry2, cx, cy, r)) {
    cout << "NO" << endl;
  } else {
    cout << "YES" << endl;
  }
}

参考

Discussion