第十六届四川省大学生程序设计竞赛
F. Isoball: 2D Version
题意：给定一个圆和一个矩阵还有圆行走的方向，问圆往这个方向是否能让整个圆都在矩阵内
分析：先判断圆是否能在矩阵里，再看圆心运动轨迹是否与小矩阵有焦点（只要圆心在小矩阵就一定在矩阵里）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define x first
#define y second
typedef long double ld;
void sol(){ld x, y, r, vx, vy; // 圆的初始位置 半径 速度向量ld lx, ly, rx, ry, llx, lly, rrx, rry; // 矩形位置cin >> x >> y >> r >> vx >> vy >> lx >> ly >> rx >> ry;llx = lx + r, lly = ly + r, rrx = rx - r, rry = ry - r;if (abs(rx-lx)<2*r || abs(ry-ly)<2*r) {//判断圆能否被矩形完全包围cout << "No" << endl;return; }if (vx == 0) { // 当圆沿着y轴方向能否直接进入矩形if (llx <= x && x <= rrx) {//x轴位置是否符合if ((vy < 0 && y >= lly) || (vy >= 0 && y <= rry)) {//往下并且圆在上面或者往上并且圆在下面 cout << "Yes" << endl;return;}}cout << "No" << endl;return;}if (vy == 0) {//当圆沿着x轴方向能否直接进入矩形if (lly <= y && y <= rry ) {if ((vx < 0 && x >= llx) || (vx >= 0 && x <= rrx)) {cout << "Yes" << endl;return;}}cout << "No" << endl;return;}pair<ld, ld> o1, o2, o3, o4;// 圆心与四条边相交的位置，o1o3为与两边相交可能位置// Δy/Δx=vx/vy Y=y+Δy :Y=y+(Δx*vy)/vx X=x+Δx :X=x+(Δy*vx)/vyo1.x = llx, o1.y = vy * (o1.x - x) / vx + y;//x=llxo3.x = rrx, o3.y = vy * (o3.x - x) / vx + y; //x==rryo2.y = rry, o2.x = vx * (o2.y - y) / vy + x;//y==rryo4.y = lly, o4.x = vx * (o4.y - y) / vy + x;//y==lly// cout<<o1.x<<" "<<o1.y<<"\n"<<o2.x<<" "<<o2.y<<"\n"<<o3.x<<" "<<o3.y<<"\n"<<o4.x<<" "<<o4.y<<"\n";// 从圆心出发的射线能否与矩形四条边相交，检查oi是否会与矩形边相交bool s1 = 1, s2 = 1, s3 = 1, s4 = 1;if (vx > 0) {//方向 if (o1.x < x)s1 = 0;if (o2.x < x)s2 = 0;if (o3.x < x)s3 = 0;if (o4.x < x)s4 = 0;} else {if (o1.x > x)s1 = 0;if (o2.x > x)s2 = 0;if (o3.x > x)s3 = 0;if (o4.x > x)s4 = 0;}if (vy > 0) {if (o1.y < y)s1 = 0;if (o2.y < y)s2 = 0;if (o3.y < y)s3 = 0;if (o4.y < y)s4 = 0;} else {if (o1.y > y)s1 = 0;if (o2.y > y)s2 = 0;if (o3.y > y)s3 = 0;if (o4.y > y)s4 = 0;}if (o1.y < lly || o1.y > rry)//在有效区间内 s1 = 0;if (o2.x < llx || o2.x > rrx)s2 = 0;if (o3.y < lly || o3.y > rry)s3 = 0;if (o4.x < llx || o4.x > rrx)s4 = 0;// 若有一个点与矩形相交，说明在矩形内部if (s1 || s2 || s3 || s4) {cout << "Yes" << endl;return;}cout << "No" << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)sol();return 0;
}