poj 3714 Raid【(暴力+剪枝) || (分治法+剪枝)】
题目:
Raid
Description After successive failures in the battles against the Union, the Empire retreated to its last stronghold. Depending on its powerful defense system, the Empire repelled the six waves of Union's attack. After several sleepless nights of thinking, Arthur, General The general soon started a raid to the stations by N special agents who were paradroped into the stronghold. Unfortunately they failed to land at the expected positions due to the attack by the Empire Air Force. As an experienced general, Arthur Input The first line is a integer T representing the number of test cases. Output For each test case output the minimum distance with precision of three decimal placed in a separate line. Sample Input 2 Sample Output 1.414 Source |
题意:
算法:
分治法:
代码:
/****************************************************************
D Accepted 4892 KB 1391 ms C++ 1222 B 2013-07-24 10:23:05
算法:暴力 + 剪枝
题意:给一个点集A,一个点集B,
求min(distance(x, y))(x∈A,y∈B)
思路:把两个集合中的点弄在一个数组中排序(分开暴力会TLE)
排序方法:x 坐标从左到右, y坐标从下到上
排序前:先找出 A 中任意一点p1和 B 中任意一点 p2的距离,记为 mini 【那么最后求出的结果不会比 mini 大。。了解!】
排序后:暴力枚举每两点的距离,不断更新 mini
剪枝优化:p[j].x-p[i].x >= mini,则 break
因为如果是这种情况,那么加上 y 坐标上的就一定会 > mini
直接跳出这一点,遍历下一点即可。
**********************************************************************/
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std; const int maxn = 100000+10;
const double INF = 1000000000*2; int n,N;
struct Point{
double x,y;
int flag;
}p[maxn*2]; bool cmp(Point a, Point b)
{
if(a.x == b.x) return a.y <= b.y;
else return a.x < b.x;
}
double dist(Point a, Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
} double minDist()
{
double mini = dist(p[0], p[n]); //排序前,找出 A 集合和 B 集合任意一点间距离 sort(p,p+N,cmp); //排序 for(int i = 0; i < N-1; i++)
{
for(int j = i+1; j < N; j++)
{
if(p[i].flag == p[j].flag) continue; //属于同一集合
if(p[j].x-p[i].x >= mini) break; // x 轴的距离就已经不小于当前最优解了,直接跳出第二层循环找下一点 double tmp = dist(p[i],p[j]); //求距离,并且更新
mini = min(mini, tmp);
}
}
return mini;
} int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
N = 2*n;
for(int i = 0; i < n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].flag = 1;
}
for(int i = n; i < N; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].flag = 0;
}
double ans = minDist();
printf("%.3lf\n", ans);
}
return 0;
}
/****************************************************************
D Accepted 4896 KB 1704 ms C++ 1678 B 2013-07-24 15:47:05
算法:分治法 + 剪枝
题意:给一个点集A,一个点集B,
求min(distance(x, y))(x∈A,y∈B)
思路:把两个集合中的点弄在一个数组中排序
排序方法:x 坐标从左到右, y坐标从下到上(PS: y左边也可以不排序) 剪枝优化:p[j].x-p[i].x >= mini,则 break
因为如果是这种情况,那么加上 y 坐标上的就一定会 > mini
直接跳出这一点,遍历下一点即可。
分治法:先把问题分解成左右两个子问题递归求解,然后再合并即可【一般是分成相等的两半效率最高了】
对于此问题:
先分成:从左边到中间 和 从中间到右边这两个子问题求出一个可能的最小距离
然后再合并:从左边(左边到中间的那段)取出一个点 u,
从右边取出一个点 v
找出最小的dist(u,v)与前面的子问题中求出的最小距离比较即可
**********************************************************************/
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std; const int maxn = 100000+10;
const double INF = 1000000000*2; struct Point{
double x,y;
int flag;
}p[2*maxn];
int index[2*maxn]; bool cmp(Point a, Point b)
{
return a.x < b.x;
} double dist(Point a, Point b)
{
if(a.flag != b.flag)
return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
else return INF; /** 两点属于同一集合 */
} double min_dist(int left, int right) /**[left, right) 左闭右开区间 */
{
if(right - left == 1) return INF; /** one point 只有一个点 */
if(right - left == 2) return dist(p[right],p[right+1]); /** two point 正好两个点 */ int mid = left+(right-left)/2; /** 分治法第一步:划分成[left, mid)和[mid, right) */ double Min = min(min_dist(left, mid), min_dist(mid, right)); /** 分治法第二步:递归求解 */ int L = 0; /**记录每次合并找的点数*/
/**向左向右分别找时记得剪枝优化否则还是会 TLE **/
for(int i = mid-1; i >= left && p[mid-1].x-p[i].x < Min; i--)
{ /** 分治法第三步:合并(1) --- 从分界点开始往左找到可能的点的最左边下标边界 */
index[L++] = i;
}
int Mid_Index = L; /** 记录往左找时, 第一个点的下标 */
for(int i = mid; i < right && p[i].x-p[mid-1].x < Min; i++)
{ /** 分治法第三步:合右边并(2) --- 从分界点开始往右找到可能的点的最右边的下标边界*/
index[L++] = i;
} double distance = INF;
for(int i = 0; i < Mid_Index; i++) /** 遍历往左找的点*/
{/** 分治法第三步:正式合并(3) --- dist(从左边选择的点, 从右边选择的点)*/
for(int j = Mid_Index; j < L; j++) /** 遍历往右找的点*/
{
Min = min(Min, dist(p[index[i]], p[index[j]])); /** 更新最短距离*/
}
}
return Min;
} int main()
{
int T;
int n,N;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
N = 2*n;
for(int i = 0; i < n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].flag = 0;
}
for(int i = n; i < N; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
p[i].flag = 1;
}
sort(p,p+N,cmp); double ans = min_dist(0, N);
printf("%.3lf\n", ans);
}
return 0;
}
最新文章
- 制作CAB包
- java selenium (五) 元素定位大全
- bigdecimal 保留小数位
- 下拉tableView实现类似微信中带图的灰色背景
- IOS SDWebImage实现原理详解
- golang thrift 源码分析,服务器和客户端究竟是如何工作的
- python twisted启动定时服务
- VS2013的virtualpath在当前应用程序根的外部
- liunx之:wps for liunx的安装经验
- jquery 自动补全控件(支持IE6)待整理
- 利用C语言强行点击置灰的按钮
- Struck: Structrued Output Tracking with Kernels 论文笔记
- 无废话WCF入门教程五[WCF的通信模式]
- 动手实现Expression翻译器1
- 利用<;meta http-equiv=";refresh"; content=";0;URL=?id=&#39;.$id.&#39;"; />;一条一条的更新数据
- sleep() 和 wait() 有什么区别?
- JAVA基础3——常见关键字解读(2)
- 【Dubbo 源码解析】02_Dubbo SPI
- 06-jQuery的文档操作
- Vulnhub Breach1.0