首页 > ACM题库 > HDU-杭电 > HDU 3124-Moonmist-分治-[解题报告]HOJ
2014
03-03

HDU 3124-Moonmist-分治-[解题报告]HOJ

Moonmist

问题描述 :

An Unidentified Flying Object (Commonly abbreviated as UFO) is the popular term for any aerial phenomenon whose cause cannot be easily or immediately identified. We always believe UFO is the vehicle of aliens. But there is an interrogation about why UFO always likes a circular saucer? There must be a reason. Actually our scientists are developing a new traffic system “Moonmist”. It is distinguished from the traditional traffic. We use circular saucers in this new traffic system and the saucers moves extremely fast. When our scientists did their test, they found that traffic accident was too hard to be avoided because of the high speed of the advanced saucer. They need us to develop a system that can tell them the nearest saucer. The distance between two saucers is defined as the shortest distance between any two points in different saucers.

输入:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of an integer N, indicating the number of saucers. Each saucer is represented on a single line, consisting of three integers X, Y, R, indicating the coordinate and the radius. You can assume that the distance between any two saucers will never be zero.

输出:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of an integer N, indicating the number of saucers. Each saucer is represented on a single line, consisting of three integers X, Y, R, indicating the coordinate and the radius. You can assume that the distance between any two saucers will never be zero.

样例输入:

1
2
0 0 1
10 10 1

样例输出:

12.142136

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3124

这个题目开始拿到的时候就一心想用平面最近点对的方法去套,折腾了好一会都没得出结果,无奈在网上搜解题报告发现这篇博文

http://blog.sina.com.cn/s/blog_6e7b12310100qnex.html

一看见二分半径,似乎就明白了,可惜这个不是重点,重点是怎么在线性时间内判断是否存在相交的圆,这个就要用到扫描线的

方法,这个方法我看了好一会才有点眉目,阅读了大神的代码后自己尝试写的代码,自己觉得重要的部分稍微加了点注释,思想

是别人的建议不要在此逗留太久,去上面的博客链接看看吧!

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <set>
#include <algorithm>
using namespace std;
#define left Left
#define right Right
#define eps 1e-8
#define maxn 60000
double x[maxn],y[maxn],r[maxn];
int left[maxn],right[maxn],up[maxn],rank_up[maxn];
int n;
set<int> my_set;
double mid;
bool cmp_left(const int &a,const int &b)
{
    return x[a]-r[a] < x[b]-r[b];
}
bool cmp_right(const int &a,const int &b)
{
    return x[a]+r[a] < x[b]+r[b];
}
bool cmp_up(const int &a,const int &b)
{
    if(y[a]==y[b])
    return  x[a] < x[b];
    else return y[a] < y[b];
}
double my_sqr(double a)
{
    return a*a;
}
bool is_cross(int a,int b)//检测高度排名为a和b的圆是否相交
{
    a=up[a],b=up[b];
    double t1,t2;
    t1=my_sqr(x[a]-x[b])+my_sqr(y[a]-y[b]),t2=my_sqr(r[a]+r[b]+mid+mid);
    if(t1<=t2)
    return true;//表示相交
    return false;
}
/*
 * 这个函数插入的是当前在集合里面圆心y值,每次再插入
 * 的同时返回插入的位置,由于set是排序了的,所以前后相邻位置
 * 的大小关系也是相邻的,那么在检测当前插入的这个圆是否与当前集合里面的圆相交
 * 就只要判断当前插入的圆与其上下两个圆是否相交就OK了
 */
bool insert(int a)//这个函数在插入的同时检测是否发生相交的情况
{
    set<int>::iterator it=my_set.insert(a).first;//这个first指向当前插入的这个元素位置的迭代器
    if(it!=my_set.begin())
    {
        if(is_cross(a,*--it))//相交
        return true;
        it++;//恢复
    }
    //注意set开始位置是元素,结束位置是位置,所以处理起来就不同了
    if(++it!=my_set.end())
    {
        if(is_cross(a,*it))
        return true;
    }
    return false;
}
bool is_ok()
{
    my_set.clear();
    int i=0,j=0;
    while(i<n || j<n)
    {
        if(j==n ||(i!=n && x[left[i]]-r[left[i]]-mid<x[right[j]]+r[right[j]]+mid))
        {
            /*这里代码在处理的时候插入的是y坐标的排名,这样的好处是插入set是
             *排序的,这样就能保证set某个元素的前后位置就是在真实圆的上下相邻位置,所以这里每次插入的是排名
             *也就是插入的不是元素,是排名,在插的时候直接插你排第几
             */
            if(insert(rank_up[left[i++]]))
                return true;//
        }
        else
        my_set.erase(rank_up[right[j++]]);
    }
    return false;
}
double find_ans()
{
    double l=0,ri=sqrt(my_sqr(x[0]-x[1])+my_sqr(y[0]-y[1]))-r[0]-r[1];//求最小的距离嘛,左值为0,右边随便取一个两个圆距离就OK了
    while(l+eps<ri)//这里不加eps可能对于某些测试数据导致超时
    {
        mid=(l+ri)/2;
        if(is_ok())
        ri=mid;
        else
        l=mid;
    }
    printf("%.6lf\n",l+ri);
    return 0;
}
int main()
{
    int t,i,j,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        scanf("%lf%lf%lf",&x[i],&y[i],&r[i]);
        for(i=0;i<n;i++)
        {
            left[i]=i;
            right[i]=i;
            up[i]=i;
        }
        sort(left,left+n,cmp_left);
        sort(right,right+n,cmp_right);
        sort(up,up+n,cmp_up);
        for(i=0;i<n;i++)
        rank_up[up[i]]=i;
        find_ans();
    }
    return 0;
}

参考:http://blog.csdn.net/sunrain_chy/article/details/9955445


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  4. [email protected]

  5. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮