动画：让你看到各种排序算法的运行
廉颇老矣 (装B一下)
May
10
对于一个felix能做出4题的比赛，我想这次的题目实在是够简单了。毕竟是初赛。
A题，服务器173上的A题（据测试，至少有4台独立的服务器170~173跑着POJ的程序）
就是那个求和的程序，那显然应该速战速决1AC——这是我机器上14:01:02写完的程序：
173上的B题，也就是企鹅豆豆的那题，让我想起了打豆豆的笑话。
一眼看过去，觉得是一个超简单的题目，sort一遍，然后O(n^2)遍历求出一个i，比penguin[i]高且力气大的企鹅是最多的。
通过了test case，然后提交，WA。
暂时忽略之，然后看了CDE题的题意，发现还是应该先搞B。
于是回过头来，仔细想了一下，发现自己SB了：
以H(Height)和S(Strength)建立一个直角坐标系，把所有的企鹅放进去
然后对任意两个企鹅a, b: 如果La < Lb 且 Sa < Sb，那么画一条从a到b的有向线段，于是就构成了一张图，或者是一个有交叉的森林，或者又可以叫做拓扑图？反正就是那么一个东西，然后有那么几个点只有出度没有入度（暂且称之为源点），有那么几个点只有入度没有出度（暂且称之为终点），我们要找一条从某一个源点到某一个终点的最长的路线。顺着这个思路，于是就想到了BFS：对每一个点都BFS过去，最后遍历所有的点，找出最大的深度，就是所求结果了。很快code完，提交，TLE。囧。看了一下，发现自己非常SB地在每次BFS以后都把所有的点的depth初始化了。注释掉这一句，提交，AC，14:32:58。
——坦白说这是第一次在比赛中用BFS AC题目，虽然我是BFS队里的。
后来Sandy和Boluor都来问我情况，发现我AC了这题，但是他们卡住了。他们的思路是把所有的企鹅按高度排序，然后使用DP求最长严格递增子序列的长度。不过他们忽略了两个高度相等的情况，于是WA了很久。后来sandy发现这个trick后ac了，boluor则继续wa，直到改用我说的BFS方法才AC。比赛后仔细想了想，如果使用DP，那么求这个问题的最优方法是O(NlogN)（详见某年国家队的论文，我不会=.=），一般的DP是O(n^2)，而我的BFS方法也是O(n^2)。之前会TLE是因为了SB的做法导致了极端情况；实际上为了避免可能存在的极端情况，可以通过STL的shuffle函数这样的方式来初始化BFS的顺序，这样就可以保证算法不会退化，但是恐怕是难以优化到O(NlogN)了。还好数据量不大。
C题Ball，是计算几何，本能的抵触，大概想了一下，发现有n种情况要考虑，暂时忽略之。
D题String，是字符串处理的，看起来估计要自动机去整它，无视之。
E题PaperCut，DP，或者说分治。由于Jieyu说他AC了，而且基本上差不多是硬搞了，于是就去做。公式是很容易推的，但是code完以后样例过不了。发现把min写成max了，囧，改之，还是不对。后来发现是切割后的处理不对，因为这是分格子，所以对于切割的点 i ，一边是 i-1 ，另一边是 i 。我把 -1 漏掉了。改过来以后通过了两个样例的数据。但是TLE了。这个时候是已经加了cache[10][10][10][10][50]来保存中间计算结果的。jieyu说需要预处理，先求出所有的cache[x1][y1][x2][y2][0]。想了一会儿，推出一个结论：
第一个等式的前两项很好理解，最后一项其实也很容易推知（这是去年个人选拔赛的某一题的结论了，印象中一共遇到两次）
第二个等式那基本上就是废话。
至此思路是完全正确了，但是就这么着耗了我将近2个小时，直到17:52左右才终于通过了test case，提交AC。
发现错误出现在两个方面：
1。二分的过程出了问题，又是上面的那个问题，不过这次是+1。
2。被jieyu误导了，或者说是我自己的代码不对，通过4层for循环初始化并没有求出所有的cache[x1][y1][x2][y2][0]。于是在执行过程中也调用calcache函数，但是还是出错，到最后才悟道，原来同样的4层for循环初始化也没有求出所有的sum[x1][y2][x2][y2]。于是放弃初始化，全部改成在过程中求解（反正每个就求一次，时间是一样的），然后才终于AC。
这里贴一个整洁一点的代码吧：
晚上去吃饭的时候听Sandy说了一下C题Ball的思路，其实只要标准化一下，把A球置为静止，B球相对A运动，那么之后的处理就相当简单了。代码比较快就写完了，但是tic的提交系统已经关闭了，怨念阿：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
A题，服务器173上的A题（据测试，至少有4台独立的服务器170~173跑着POJ的程序）
就是那个求和的程序，那显然应该速战速决1AC——这是我机器上14:01:02写完的程序：
#include<iostream>
using namespace std;
int main(){
int n, i, t, sum = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i){
scanf("%d", &t);
sum += t;
}
printf("%d\n", sum);
return 0;
}
using namespace std;
int main(){
int n, i, t, sum = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i){
scanf("%d", &t);
sum += t;
}
printf("%d\n", sum);
return 0;
}
173上的B题，也就是企鹅豆豆的那题，让我想起了打豆豆的笑话。
一眼看过去，觉得是一个超简单的题目，sort一遍，然后O(n^2)遍历求出一个i，比penguin[i]高且力气大的企鹅是最多的。
通过了test case，然后提交，WA。
暂时忽略之，然后看了CDE题的题意，发现还是应该先搞B。
于是回过头来，仔细想了一下，发现自己SB了：
以H(Height)和S(Strength)建立一个直角坐标系，把所有的企鹅放进去
然后对任意两个企鹅a, b: 如果La < Lb 且 Sa < Sb，那么画一条从a到b的有向线段，于是就构成了一张图，或者是一个有交叉的森林，或者又可以叫做拓扑图？反正就是那么一个东西，然后有那么几个点只有出度没有入度（暂且称之为源点），有那么几个点只有入度没有出度（暂且称之为终点），我们要找一条从某一个源点到某一个终点的最长的路线。顺着这个思路，于是就想到了BFS：对每一个点都BFS过去，最后遍历所有的点，找出最大的深度，就是所求结果了。很快code完，提交，TLE。囧。看了一下，发现自己非常SB地在每次BFS以后都把所有的点的depth初始化了。注释掉这一句，提交，AC，14:32:58。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct penguin{
int h, s;
int dep;
vector<int>q;
};
int n;
penguin p[1024];
bool cmp(const penguin &a , const penguin &b){
return a.h < b.h;
}
void bfs(int i){
vector<int>q;
int a, b, c, t;
int dep = 0;
q.push_back(i);
a = 1, b = 0;
while(b < a){
c = q[b]; //当前的企鹅
dep = p[c].dep;
for (unsigned int j = 0; j < p[c].q.size(); ++j){
t = p[c].q[j];
if(dep+1 > p[t].dep){
p[t].dep = dep + 1;
q.push_back(t);
a++;
}
}
b++;
}
q.clear();
}
int main(){
int i, j, ans = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i){
scanf("%d%d", &p[i].h, &p[i].s);
p[i].dep = 1;
}
for (i = 0; i < n; ++i){
for (j = 0; j < n; ++j){
if(i == j) continue;
if(p[j].h > p[i].h && p[j].s > p[i].s){
p[i].q.push_back(j);
}
}
}
ans = 0;
for(i = 0; i < n; ++i){
//printf("i = %d\n", i);
bfs(i);
for(j = 0; j < n; ++j){
//printf("%d ", p[j].dep);
ans = max(ans, p[j].dep);
//p[j].dep = 1;
}
//printf("\n");
}
printf("%d\n", ans);
return 0;
}
#include <algorithm>
#include <vector>
using namespace std;
struct penguin{
int h, s;
int dep;
vector<int>q;
};
int n;
penguin p[1024];
bool cmp(const penguin &a , const penguin &b){
return a.h < b.h;
}
void bfs(int i){
vector<int>q;
int a, b, c, t;
int dep = 0;
q.push_back(i);
a = 1, b = 0;
while(b < a){
c = q[b]; //当前的企鹅
dep = p[c].dep;
for (unsigned int j = 0; j < p[c].q.size(); ++j){
t = p[c].q[j];
if(dep+1 > p[t].dep){
p[t].dep = dep + 1;
q.push_back(t);
a++;
}
}
b++;
}
q.clear();
}
int main(){
int i, j, ans = 0;
scanf("%d", &n);
for (i = 0; i < n; ++i){
scanf("%d%d", &p[i].h, &p[i].s);
p[i].dep = 1;
}
for (i = 0; i < n; ++i){
for (j = 0; j < n; ++j){
if(i == j) continue;
if(p[j].h > p[i].h && p[j].s > p[i].s){
p[i].q.push_back(j);
}
}
}
ans = 0;
for(i = 0; i < n; ++i){
//printf("i = %d\n", i);
bfs(i);
for(j = 0; j < n; ++j){
//printf("%d ", p[j].dep);
ans = max(ans, p[j].dep);
//p[j].dep = 1;
}
//printf("\n");
}
printf("%d\n", ans);
return 0;
}
——坦白说这是第一次在比赛中用BFS AC题目，虽然我是BFS队里的。
后来Sandy和Boluor都来问我情况，发现我AC了这题，但是他们卡住了。他们的思路是把所有的企鹅按高度排序，然后使用DP求最长严格递增子序列的长度。不过他们忽略了两个高度相等的情况，于是WA了很久。后来sandy发现这个trick后ac了，boluor则继续wa，直到改用我说的BFS方法才AC。比赛后仔细想了想，如果使用DP，那么求这个问题的最优方法是O(NlogN)（详见某年国家队的论文，我不会=.=），一般的DP是O(n^2)，而我的BFS方法也是O(n^2)。之前会TLE是因为了SB的做法导致了极端情况；实际上为了避免可能存在的极端情况，可以通过STL的shuffle函数这样的方式来初始化BFS的顺序，这样就可以保证算法不会退化，但是恐怕是难以优化到O(NlogN)了。还好数据量不大。
C题Ball，是计算几何，本能的抵触，大概想了一下，发现有n种情况要考虑，暂时忽略之。
D题String，是字符串处理的，看起来估计要自动机去整它，无视之。
E题PaperCut，DP，或者说分治。由于Jieyu说他AC了，而且基本上差不多是硬搞了，于是就去做。公式是很容易推的，但是code完以后样例过不了。发现把min写成max了，囧，改之，还是不对。后来发现是切割后的处理不对，因为这是分格子，所以对于切割的点 i ，一边是 i-1 ，另一边是 i 。我把 -1 漏掉了。改过来以后通过了两个样例的数据。但是TLE了。这个时候是已经加了cache[10][10][10][10][50]来保存中间计算结果的。jieyu说需要预处理，先求出所有的cache[x1][y1][x2][y2][0]。想了一会儿，推出一个结论：
引用
记f(x1, y1, x2, y2) = cache[x1][y1][x2][y2][0]， xm = (x1+x2)/2，那么
f(x1,y1, x2,y2) = f(x1,y1, xm, y2) + f(xm, y1, x2, y2) + sum(x1,y1, xm,y2) * sum(xm,y1, x2,y2)
而sum(x1,y1, x2,y2) = sum(x1,y1, xm,y2) + sum(xm,y1, x2,y2)
f(x1,y1, x2,y2) = f(x1,y1, xm, y2) + f(xm, y1, x2, y2) + sum(x1,y1, xm,y2) * sum(xm,y1, x2,y2)
而sum(x1,y1, x2,y2) = sum(x1,y1, xm,y2) + sum(xm,y1, x2,y2)
第一个等式的前两项很好理解，最后一项其实也很容易推知（这是去年个人选拔赛的某一题的结论了，印象中一共遇到两次）
第二个等式那基本上就是废话。
至此思路是完全正确了，但是就这么着耗了我将近2个小时，直到17:52左右才终于通过了test case，提交AC。
发现错误出现在两个方面：
1。二分的过程出了问题，又是上面的那个问题，不过这次是+1。
2。被jieyu误导了，或者说是我自己的代码不对，通过4层for循环初始化并没有求出所有的cache[x1][y1][x2][y2][0]。于是在执行过程中也调用calcache函数，但是还是出错，到最后才悟道，原来同样的4层for循环初始化也没有求出所有的sum[x1][y2][x2][y2]。于是放弃初始化，全部改成在过程中求解（反正每个就求一次，时间是一样的），然后才终于AC。
这里贴一个整洁一点的代码吧：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int d[10][10];
int sum[10][10][10][10];
int cache[10][10][10][10][50];
int n, m, k;
int calsum(int xs, int ys, int xe, int ye){
int ans = sum[xs][ys][xe][ye];
if(ans < 0){
if(xs == xe){
ans = 0;
int x1, y1;
for(x1 = xs; x1 <= xe; x1++){
for(y1 = ys; y1 <= ye; y1++){
ans += d[x1][y1];
}
}
}else{
int xm = (xs + xe) / 2;
int sum1 = calsum(xs, ys, xm, ye);
int sum2 = calsum(xm+1, ys, xe, ye);
ans = sum1 + sum2;
}
sum[xs][ys][xe][ye] = ans;
}
return ans;
}
int calcache(int xs, int ys, int xe, int ye){
int ans = cache[xs][ys][xe][ye][0];
if(ans < 0){
if(xs == xe){
if(ys == ye){
ans = 0;
}else{
int ym = (ys + ye) / 2;
int cache1 = calcache(xs, ys, xe, ym);
int cache2 = calcache(xs, ym+1, xe, ye);
ans = cache1 + cache2 + calsum(xs,ys,xe,ym) * calsum(xs,ym+1,xe,ye);
}
}else{
int xm = (xs + xe) / 2;
int cache1 = calcache(xs, ys, xm, ye);
int cache2 = calcache(xm+1, ys, xe, ye);
ans = cache1 + cache2 + calsum(xs,ys,xm,ye) * calsum(xm+1,ys,xe,ye);
}
cache[xs][ys][xe][ye][0] = ans;
}
return ans;
}
int f(int xs,int ys,int xe,int ye,int k){
if(xs < 0 || xe < 0 || ys < 0 || ye < 0 || xs > xe || ys > ye) return 0;
int ans = cache[xs][ys][xe][ye][k];
if(ans == -1){
if(k == 0){
ans = calcache(xs, ys, xe, ye);
}else{
int i, j;
int v1, v2;
ans = -1;
for(i = xs; i <= xe; ++i){
for(j = 0; j <= k - 1; ++j){
v1 = f(xs, ys, i-1, ye, j);
v2 = f(i, ys, xe, ye, k-1-j);
if(ans < 0){
ans = v1 + v2;
} else{
ans = min(ans, v1+v2);
}
}
}
for(i = ys; i <= ye; ++i){
for(j = 0; j <= k - 1; ++j){
v1 = f(xs, ys, xe, i-1, j);
v2 = f(xs, i, xe, ye, k-1-j);
if(ans < 0){
ans = v1 + v2;
} else{
ans = min(ans, v1+v2);
}
}
}
}
cache[xs][ys][xe][ye][k] = ans;
}
return ans;
}
int main(){
int i, j;
scanf("%d%d%d", &n, &m, &k);
for (i = 0; i < n; ++i){
for (j = 0; j < m; ++j){
scanf("%d", &d[i][j]);
}
}
memset(sum, -1, sizeof(sum));
memset(cache, -1, sizeof(cache));
printf("%d\n", f(0, 0, n-1, m-1, k));
return 0;
}
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int d[10][10];
int sum[10][10][10][10];
int cache[10][10][10][10][50];
int n, m, k;
int calsum(int xs, int ys, int xe, int ye){
int ans = sum[xs][ys][xe][ye];
if(ans < 0){
if(xs == xe){
ans = 0;
int x1, y1;
for(x1 = xs; x1 <= xe; x1++){
for(y1 = ys; y1 <= ye; y1++){
ans += d[x1][y1];
}
}
}else{
int xm = (xs + xe) / 2;
int sum1 = calsum(xs, ys, xm, ye);
int sum2 = calsum(xm+1, ys, xe, ye);
ans = sum1 + sum2;
}
sum[xs][ys][xe][ye] = ans;
}
return ans;
}
int calcache(int xs, int ys, int xe, int ye){
int ans = cache[xs][ys][xe][ye][0];
if(ans < 0){
if(xs == xe){
if(ys == ye){
ans = 0;
}else{
int ym = (ys + ye) / 2;
int cache1 = calcache(xs, ys, xe, ym);
int cache2 = calcache(xs, ym+1, xe, ye);
ans = cache1 + cache2 + calsum(xs,ys,xe,ym) * calsum(xs,ym+1,xe,ye);
}
}else{
int xm = (xs + xe) / 2;
int cache1 = calcache(xs, ys, xm, ye);
int cache2 = calcache(xm+1, ys, xe, ye);
ans = cache1 + cache2 + calsum(xs,ys,xm,ye) * calsum(xm+1,ys,xe,ye);
}
cache[xs][ys][xe][ye][0] = ans;
}
return ans;
}
int f(int xs,int ys,int xe,int ye,int k){
if(xs < 0 || xe < 0 || ys < 0 || ye < 0 || xs > xe || ys > ye) return 0;
int ans = cache[xs][ys][xe][ye][k];
if(ans == -1){
if(k == 0){
ans = calcache(xs, ys, xe, ye);
}else{
int i, j;
int v1, v2;
ans = -1;
for(i = xs; i <= xe; ++i){
for(j = 0; j <= k - 1; ++j){
v1 = f(xs, ys, i-1, ye, j);
v2 = f(i, ys, xe, ye, k-1-j);
if(ans < 0){
ans = v1 + v2;
} else{
ans = min(ans, v1+v2);
}
}
}
for(i = ys; i <= ye; ++i){
for(j = 0; j <= k - 1; ++j){
v1 = f(xs, ys, xe, i-1, j);
v2 = f(xs, i, xe, ye, k-1-j);
if(ans < 0){
ans = v1 + v2;
} else{
ans = min(ans, v1+v2);
}
}
}
}
cache[xs][ys][xe][ye][k] = ans;
}
return ans;
}
int main(){
int i, j;
scanf("%d%d%d", &n, &m, &k);
for (i = 0; i < n; ++i){
for (j = 0; j < m; ++j){
scanf("%d", &d[i][j]);
}
}
memset(sum, -1, sizeof(sum));
memset(cache, -1, sizeof(cache));
printf("%d\n", f(0, 0, n-1, m-1, k));
return 0;
}
晚上去吃饭的时候听Sandy说了一下C题Ball的思路，其实只要标准化一下，把A球置为静止，B球相对A运动，那么之后的处理就相当简单了。代码比较快就写完了，但是tic的提交系统已经关闭了，怨念阿：
#include<iostream>
#include<cmath>
using namespace std;
struct coord_t{
double x, y;
coord_t(){};
coord_t(double _x, double _y):x(_x),y(_y){}
};
struct ball{
coord_t p, v;
double r;
};
inline int cmp(const double &a, const double &b){
if(fabs(a-b) < 1e-9) return 0;
if(a - b > 0) return 1;
else return 0;
}
inline double pow2(double a){
return a * a;
}
inline double len2(const coord_t &a){
return (pow2(a.x) + pow2(a.y));
}
inline double len(const coord_t &a){
return sqrt(len2(a));
}
inline double dist2(const coord_t &a, const coord_t &b){
return (pow2(b.x-a.x) + pow2(b.y - a.y));
}
int main(){
int T;
double xa, ya, vax, vay, ra, xb, yb, vbx, vby, rb;
ball a, b;
scanf("%d", &T);
while (T--){
scanf("%lf%lf%lf%lf%lf", &xa, &ya, &vax, &vay, &ra);
scanf("%lf%lf%lf%lf%lf", &xb, &yb, &vbx, &vby, &rb);
// 标准化，把a放在原点，速度置为0
a.p.x = 0, a.p.y = 0,
a.v.x = 0, a.v.y = 0,
a.r = ra;
// b就要做相应的调整了
b.p.x = xb - xa, b.p.y = yb - ya,
b.v.x = vbx - vax, b.v.y = vby - vay,
b.r = rb;
if(cmp(dist2(a.p, b.p), pow2(a.r + b.r)) == 0){
// 两个球本来就是靠在一起的
printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
0.0, xa, ya, xb, yb);
}else{
// 本来没靠在一起
double A, B, C, Dab;
//求出b的运动轨迹的直线方程Ax + By + C = 0
A = b.v.y, B = -b.v.x, C = b.v.x * b.p.y - b.v.y * b.p.x;
//求出a点到b运动轨迹的距离
Dab = fabs(A * a.p.x + B * a.p.y + C) / sqrt(pow2(A) + pow2(B));
if(cmp(b.v.x, 0) == 0 && cmp(b.v.y == 0) || cmp(Dab, a.r + b.r) < 0){
//如果根本不可能相碰(b不动，或者距离大于ab的半径和)
printf("Impossible\n");
continue;
}
//b到a的向量
coord_t ba(a.p.x-b.p.x, a.p.y-b.p.y);
//b的运动方向向量
coord_t bc(b.v.x, b.v.y);
//两个向量的夹角
double cosABC = ba.x * bc.y + ba.y * bc.x;
cosABC = cosABC / (len(ba) * len(bc));
//夹角小于0，说明B远离A移动
if(cmp(cosABC, 0) <= 0){
printf("Impossible\n");
continue;
}
// 下面是会相遇的情况
// b运行到a点的时候两球相碰，则ae = ra + rb
// <--d----e----<-----b
// | /
// | /
// | /
// |/
// a
double db, de, eb, ae, da = Dab;
ae = a.r + b.r;
db = sqrt(len2(ba)-pow2(da));
de = sqrt(pow2(ae)-pow2(da));
eb = db - de;
//求出时间
double time = eb / len(b.v);
//求出a坐标
xa = xa + vax * time;
ya = ya + vay * time;
//求出b坐标
xb = xb + vbx * time;
yb = yb + vby * time;
printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
time, xa, ya, xb, yb);
}
}
return 0;
}
#include<cmath>
using namespace std;
struct coord_t{
double x, y;
coord_t(){};
coord_t(double _x, double _y):x(_x),y(_y){}
};
struct ball{
coord_t p, v;
double r;
};
inline int cmp(const double &a, const double &b){
if(fabs(a-b) < 1e-9) return 0;
if(a - b > 0) return 1;
else return 0;
}
inline double pow2(double a){
return a * a;
}
inline double len2(const coord_t &a){
return (pow2(a.x) + pow2(a.y));
}
inline double len(const coord_t &a){
return sqrt(len2(a));
}
inline double dist2(const coord_t &a, const coord_t &b){
return (pow2(b.x-a.x) + pow2(b.y - a.y));
}
int main(){
int T;
double xa, ya, vax, vay, ra, xb, yb, vbx, vby, rb;
ball a, b;
scanf("%d", &T);
while (T--){
scanf("%lf%lf%lf%lf%lf", &xa, &ya, &vax, &vay, &ra);
scanf("%lf%lf%lf%lf%lf", &xb, &yb, &vbx, &vby, &rb);
// 标准化，把a放在原点，速度置为0
a.p.x = 0, a.p.y = 0,
a.v.x = 0, a.v.y = 0,
a.r = ra;
// b就要做相应的调整了
b.p.x = xb - xa, b.p.y = yb - ya,
b.v.x = vbx - vax, b.v.y = vby - vay,
b.r = rb;
if(cmp(dist2(a.p, b.p), pow2(a.r + b.r)) == 0){
// 两个球本来就是靠在一起的
printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
0.0, xa, ya, xb, yb);
}else{
// 本来没靠在一起
double A, B, C, Dab;
//求出b的运动轨迹的直线方程Ax + By + C = 0
A = b.v.y, B = -b.v.x, C = b.v.x * b.p.y - b.v.y * b.p.x;
//求出a点到b运动轨迹的距离
Dab = fabs(A * a.p.x + B * a.p.y + C) / sqrt(pow2(A) + pow2(B));
if(cmp(b.v.x, 0) == 0 && cmp(b.v.y == 0) || cmp(Dab, a.r + b.r) < 0){
//如果根本不可能相碰(b不动，或者距离大于ab的半径和)
printf("Impossible\n");
continue;
}
//b到a的向量
coord_t ba(a.p.x-b.p.x, a.p.y-b.p.y);
//b的运动方向向量
coord_t bc(b.v.x, b.v.y);
//两个向量的夹角
double cosABC = ba.x * bc.y + ba.y * bc.x;
cosABC = cosABC / (len(ba) * len(bc));
//夹角小于0，说明B远离A移动
if(cmp(cosABC, 0) <= 0){
printf("Impossible\n");
continue;
}
// 下面是会相遇的情况
// b运行到a点的时候两球相碰，则ae = ra + rb
// <--d----e----<-----b
// | /
// | /
// | /
// |/
// a
double db, de, eb, ae, da = Dab;
ae = a.r + b.r;
db = sqrt(len2(ba)-pow2(da));
de = sqrt(pow2(ae)-pow2(da));
eb = db - de;
//求出时间
double time = eb / len(b.v);
//求出a坐标
xa = xa + vax * time;
ya = ya + vay * time;
//求出b坐标
xb = xb + vbx * time;
yb = yb + vby * time;
printf("%.3lf %.3lf %.3lf %.3lf %.3lf\n",
time, xa, ya, xb, yb);
}
}
return 0;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
a目标点^+b目标点^2=(ra+rb)^2
化成：ax^2+bx+c=0
解之
d题后缀数组之，不过暴力照过