HDU 1007 WA - C语言论坛

已结贴√ 问题点数：100 回复次数：8

HDU 1007 WA

Problem Description
Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.
Input
The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.
Output
For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.
Sample Input
2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0
Sample Output
0.71
0.00
0.75

大概意思是给你N个点的横纵坐标，求出距离最近的两个点的距离的一半

总是WA，思路用分治该是没问题的

程序代码：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX 100000

typedef struct __tag_node
{
    double x, y;
} PointNode, *Point;

PointNode ss[MAX], sl[MAX], sr[MAX];

int cmpx(const void *a, const void *b)
{
    Point pa = a, pb = b;
    return (int) (pa->x - pb->x);
}

int cmpy(const void *a, const void *b)
{
    Point pa = a, pb = b;
    return (int) (pa->y - pb->y);
}

double min(double a, double b)
{
    return a < b ? a : b;
}

double dis(Point a, Point b)
{
    double dx = a->x - b->x, dy = a->y - b->y;
    return sqrt(dx * dx + dy * dy);
}

double minDis(int beg, int end)
{
    double ans;
    int i, j, l = 0, r = 0, mid = (beg + end) / 2;

    if (1 >= end - beg) return dis(&ss[beg], &ss[end]);
    if (2 == end - beg) return min(min(dis(&ss[beg], &ss[mid]), dis(&ss[mid], &ss[end])), dis(&ss[beg], &ss[end]));

    ans = min(minDis(beg, mid), minDis(mid + 1, end));

    for (i = mid + 0; i >= beg && ss[i].x + ans >= ss[mid].x; --i) sl[l++] = ss[i];
    for (i = mid + 1; i <= end && ss[i].x - ans <= ss[mid].x; ++i) sr[r++] = ss[i];

    qsort(sl, l, sizeof(PointNode), cmpy);
    qsort(sr, r, sizeof(PointNode), cmpy);

    for (i = 0; i < l; ++i)
    {
        for (j = 0; j < r; ++j)
        {
            if (sl[i].y - ans > sr[j].y) continue;
            if (sl[i].y + ans < sr[j].y) break;

            ans = min(ans, dis(&sl[i], &sr[j]));
        }
    }
    return ans;
}

int main()
{
    int i, N;

    while (1 == scanf("%d", &N) && N)
    {
        for (i = 0; i < N; ++i) scanf("%lf%lf", &ss[i].x, &ss[i].y);

        qsort(ss, N, sizeof(PointNode), cmpx);

        printf("%.2lf\n", minDis(0, N - 1) / 2);
    }
    return 0;
}

帮我想想是哪种数据过不了

[此贴子已经被作者于2017-1-5 12:46编辑过]

第 2 楼

得分:50

专门注册了个账号测试，提交你的代码显示第26行“double min(double a, double b)”类型错误，将该函数注释掉，用宏“#define min(a,b) ( ((a)>(b)) ? (b):(a) )”替代，提交后提示Time Limit Exceeded，说明结果正确，但超时。
对分治法不熟，先学习学习，待吃透后也写个试试。

第 3 楼

得分:50

分治法~嗯嗯，最近接触快排时听过，也简单运用了一下~大概是把数据按某种规则分成若干个不同的组，使每一个组的数据都有特定的规律~然后……~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 4 楼

得分:0

以下是引用xzlxzlxzl在2017-1-5 19:30:06的发言：

专门注册了个账号测试，提交你的代码显示第26行“double min(double a, double b)”类型错误，将该函数注释掉，用宏“#define min(a,b) ( ((a)>(b)) ? (b):(a) )”替代，提交后提示Time Limit Exceeded，说明结果正确，但超时。
对分治法不熟，先学习学习，待吃透后也写个试试。

使用宏会导致递归重复运算然后超时，所以必须用函数，错误应该是min函数重名，改名后提交依然失败

ps：我是用gcc提交的，没有提示错误

[fly]存在即是合理[/fly]

第 5 楼

得分:0

回复 4楼 azzbcc

以下是引用azzbcc在2017-1-6 09:04:42的发言：

使用宏会导致递归重复运算然后超时，所以必须用函数，错误应该是min函数重名，改名后提交依然失败

ps：我是用gcc提交的，没有提示错误

min函数重名，似乎我用vc<stdlib.h>里面就有min和max函数,还可以直接用来比较大小~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的就是这样~2018-08-08更~*/[/code]

第 6 楼

得分:0

找到问题了，示例代码如下，希望大家引以为戒吧

程序代码：

#include <stdio.h>

int main()
{
    double a = 1.2, b = 2;

    printf("%d\n", (int) (a - b));
    printf("%d\n", (int) (b - a));
    
    return 0;
}

[fly]存在即是合理[/fly]

第 7 楼

得分:0

这里是AC代码

程序代码：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

 
#define MAX 100000

 
typedef struct __tag_node
{
    double x, y;
} PointNode, *Point;

 
PointNode ss[MAX], sl[MAX], sr[MAX];

 
int cmpx(const void *a, const void *b)
{
    Point pa = a, pb = b;
    if (pa->x == pb->x) return 0;
    else if (pa->x > pb->x) return 1;
    else return -1;
}

 
int cmpy(const void *a, const void *b)
{
    Point pa = a, pb = b;
    if (pa->y == pb->y) return 0;
    else if (pa->y > pb->y) return 1;
    else return -1;
}

 
double low(double a, double b)
{
    return a < b ? a : b;
}

 
double dis(Point a, Point b)
{
    double dx = a->x - b->x, dy = a->y - b->y;
    return sqrt(dx * dx + dy * dy);
}

 
double minDis(int beg, int end)
{
    double ans;
    int i, j, l = 0, r = 0, mid = (beg + end) / 2;

 
    if (1 >= end - beg) return dis(&ss[beg], &ss[end]);
    if (2 == end - beg) return low(low(dis(&ss[beg], &ss[mid]), dis(&ss[mid], &ss[end])), dis(&ss[beg], &ss[end]));

 
    ans = low(minDis(beg, mid), minDis(mid + 1, end));

 
    for (i = mid + 0; i >= beg && ss[i].x + ans >= ss[mid].x; --i) sl[l++] = ss[i];
    for (i = mid + 1; i <= end && ss[i].x - ans <= ss[mid].x; ++i) sr[r++] = ss[i];

 
    qsort(sl, l, sizeof(PointNode), cmpy);
    qsort(sr, r, sizeof(PointNode), cmpy);

 
    for (i = 0; i < l; ++i)
    {
        for (j = 0; j < r; ++j)
        {
            if (sl[i].y - ans > sr[j].y) continue;
            if (sl[i].y + ans < sr[j].y) break;

 
            ans = low(ans, dis(&sl[i], &sr[j]));
        }
    }
    return ans;
}

 
int main()
{
    int i, N;

 
    while (1 == scanf("%d", &N) && N)
    {
        for (i = 0; i < N; ++i) scanf("%lf%lf", &ss[i].x, &ss[i].y);

 
        qsort(ss, N, sizeof(PointNode), cmpx);

 
        printf("%.2lf\n", minDis(0, N - 1) / 2);
    }
    return 0;
}