HDU 1007 WA - C语言论坛

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

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 楼

得分: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]

第 3 楼

得分: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]

第 4 楼

得分: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;
}

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

第 5 楼

得分:0

以下是引用xzlxzlxzl在2017-1-6 16:25:00的发言：

仍然未得要领，写那个qsort的cmpx就调试好久，现在还Runtime Error(ACCESS_VIOLATION)了，继续学习。

qsort其实就是快排的封装，用过几次就懒得自己写排序了，结果出现这个错误，我实在太粗心了

类似的还有bsearch。

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