深圳网站建设可以吗,定制设计的网站,寿光shengkun网站建设,2020房屋装修效果图题目大意
有n艘飞船和n个基地存在于二维平面上#xff0c;每艘飞船要前往一个基地#xff0c;每个基地也需要一艘飞船 设飞船和基地之间的路径为直线 是否存在n艘飞船和n个基地之间的n条路径#xff0c;他们彼此之间互不相交
思路
当飞船数量和基地数量不相等时#xff…
题目大意
有n艘飞船和n个基地存在于二维平面上每艘飞船要前往一个基地每个基地也需要一艘飞船 设飞船和基地之间的路径为直线 是否存在n艘飞船和n个基地之间的n条路径他们彼此之间互不相交
思路
当飞船数量和基地数量不相等时不满足飞船和基地的对应关系 主要是如何证明当飞船和基地数量相等时一定会有分配方案使其不会有任何交叉 我们可以构造距离最短的构造方案
假设一对相交的线段AB、CD 假设A和C是宇宙飞船B和D是基地此时我们将分配改为A连DB连C就得到的新的分配方式 将ABCD看成平行四边形那么AB、CD是四边形的两条对角线,AD、BC是四边形的两条边
而平行四边形两条对角线的和一定大于任意两条邻边的和所以我们可以把它们变为AD,BC他们之间的路径和会变短且一定不会相交
只要飞船和基地数量相同就一定会存在没有交叉的分配方式
//Author: zengyz
//2025-06-13 16:33#include bits/stdc.husing namespace std;
using i64 long long;void solve()
{int n,r;cinnr;if(nr){coutYes;}else coutNo;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int _T 1;// cin _T;while(_T --) {solve();}return 0;
}
