Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

谁给点数据啊。样例过了照样wa的要死人了啊，最小点对求解函数哪里有问题？(内附点对分而治之的代码)

Posted by ACM_Hohai at 2009-01-09 22:29:27 on Problem 3714

/// <summary>
/// 分而治之的方法进行点对的判断距离
/// </summary>
/// <param name="l"></param>
/// <param name="r"></param>
/// <returns></returns>
double mergepoint(int l,int r)
{
    double resultl=0,resultr=0,minlen=10000000;
    if(r>l+2) {
        int mid=(l+r)>>1;
        double tempdis;
        resultl=mergepoint(l,mid);
        resultr=mergepoint(mid,r);
        minlen=min(resultl,resultr);
        for(int i=mid;i>=l&&point[i].x>point[mid].x-minlen;i--) {
            for(int j=mid;j<=r&&point[j].x<point[mid].x+minlen;j++) {
                if(point[i].type!=point[j].type) {
                    tempdis=len(point[i],point[j]);
                    if(tempdis<minlen) {
                        minlen=tempdis;
                    }
                }
            }
        }
    }
    else
    {
        double distemp;
        for(int i=l;i<r;i++) {
            for(int j=l+1;j<=r;j++) {
                if(j==i) {
                    continue;
                }
                if(point[i].type!=point[j].type) {
                    distemp=len(point[i],point[j]);
                    minlen=minlen>distemp?distemp:minlen;
                }
            }
        }
    }
    return minlen;
}

Followed by:

终于过了，我原本是把两组合并处理了，所以会出现两倍的情况，也就是200000……O(∩_∩)O哈哈~ (50) ACM_Hohai 2009-01-09 23:46:54
- Re:我很怀疑你的结论.最多只有200000个点. (0) MasterLuo 2009-01-09 23:53:32
  - Re:我很怀疑你的结论.最多只有200000个点. (81) ACM_Hohai 2009-01-10 00:03:39
    - Re:我想你是理解错了...仔细看题.题描述就有200000个点. (2) MasterLuo 2009-01-10 00:10:30
      - Re:我想你是理解错了...仔细看题.题描述就有200000个点. (35) ACM_Hohai 2009-01-10 00:22:17
我感觉你的算法在所有点的y坐标都相等的时候会退化成n^2，为什么没有TLE？数据太弱？ (0) gf_lu 2009-01-10 16:09:08
- Re:我感觉你的算法在所有点的y坐标都相等的时候会退化成n^2，为什么没有TLE？数据太弱？ (55) ACM_Hohai 2009-01-11 09:41:25
  - Re:我感觉你的算法在所有点的y坐标都相等的时候会退化成n^2，为什么没有TLE？数据太弱？ (25) MasterLuo 2009-01-11 09:49:18
  - 那是所有点对间的最短距离才有鸽巢原理啊。这题voronoi图可以做，但是太麻烦了。不知道用分治算法该怎么做 (0) gf_lu 2009-01-11 10:35:58
    - Re:那是所有点对间的最短距离才有鸽巢原理啊。这题voronoi图可以做，但是太麻烦了。不知道用分治算法该怎么做 (92) ACM_Hohai 2009-01-11 16:17:02
      - 见内 (70) gf_lu 2009-01-11 17:58:51
      - Re:那是所有点对间的最短距离才有鸽巢原理啊。这题voronoi图可以做，但是太麻烦了。不知道用分治算法该怎么做 (78) gf_lu 2009-01-11 18:04:16
- 这题数据水到一定境界了... (0) moonancient 2009-01-17 03:03:01

Post your reply here:

User ID:
Password:
Title:

Content:

> /// <summary>
> /// 分而治之的方法进行点对的判断距离
> /// </summary>
> /// <param name="l"></param>
> /// <param name="r"></param>
> /// <returns></returns>
> double mergepoint(int l,int r)
> {
>     double resultl=0,resultr=0,minlen=10000000;
>     if(r>l+2) {
>         int mid=(l+r)>>1;
>         double tempdis;
>         resultl=mergepoint(l,mid);
>         resultr=mergepoint(mid,r);
>         minlen=min(resultl,resultr);
>         for(int i=mid;i>=l&&point[i].x>point[mid].x-minlen;i--) {
>             for(int j=mid;j<=r&&point[j].x<point[mid].x+minlen;j++) {
>                 if(point[i].type!=point[j].type) {
>                     tempdis=len(point[i],point[j]);
>                     if(tempdis<minlen) {
>                         minlen=tempdis;
>                     }
>                 }
>             }
>         }
>     }
>     else
>     {
>         double distemp;
>         for(int i=l;i<r;i++) {
>             for(int j=l+1;j<=r;j++) {
>                 if(j==i) {
>                     continue;
>                 }
>                 if(point[i].type!=point[j].type) {
>                     distemp=len(point[i],point[j]);
>                     minlen=minlen>distemp?distemp:minlen;
>                 }
>             }
>         }
>     }
>     return minlen;
> }

Home Page Go Back To top