👌
ARC 051 | A - 塗り絵
問題
考えたこと
円が赤に、長方形が青に、重なる部分は紫になる。
赤が存在しないとうことは、以下のように円を長方形が覆っていた場合になる。
この場合、以下の緑の4点が長方形の内側にあるかどうか判定すればいい。
青が存在しないということは、以下のように長方形を円が覆っていた場合になる。
この場合は、以下の緑の4点と円の中心との距離が
コード
#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