自己写的代码通过了自己的测试，却通不过poj的测试（貌似这也没什么）
从网上找的其它两分代码能通过poj的测试，却通不过我的测试（原因很简单，它们的输出结果不一样。。。）
我的WA程序至今原因不明，下面也贴出来让大家帮俺找找错。。谢谢

sanding:/mnt/3/shiyan/C/algorithm # ./island222 < island.txt 
Case 1: 2
Case 2: 1
Case 3: 2
Case 4: 1
Case 5: 6
Case 6: 2
sanding:/mnt/3/shiyan/C/algorithm # ./island111 < island.txt 
Case 1: 2
Case 2: 2
Case 3: 2
Case 4: 2
Case 5: 6
Case 6: 2
sanding:/mnt/3/shiyan/C/algorithm # cat island.txt 
3 2
0 0
1 2
4 0

3 5
4 3
2 3
6 -9

4 2
0 0
2 0
4 0
6 0

2 1000000
1 1
1 -1

17 5
3 4 
4 3
4 5
4 4
-1 2
4 1
-4 0
3 3
3 5
26 2
3 1
0 0
0 1
-1 3
19 5
11 4
12 -3

4 2
1 1
1 -2
100 1
101 2

0 0

下面是那两个程序，大家可以贴上去试试。。。

island111.cpp :

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

const int N = 1000;
const double EPS = 1e-7;

struct E { double a, b; } e[N];
int n, d;
bool ava[N];
double p[N];

inline int dblcmp(double a, double b) {
	if( fabs(a-b) < EPS ) return 0;
	if( a-b > 0 ) return 1;
	return -1;
}

	bool operator<(const E& a, const E& b) {
		if(dblcmp(a.a, b.a) == 0)
			return dblcmp(a.b, b.b) == 1;
		return dblcmp(a.a, b.a) == -1;
	}


int main() {
	int i, j, x, y;
	int tc = 0;
	while(scanf("%d %d", &n, &d), n + d) {
		tc++;
		int ok = 1;
		for(i = 0; i < n; ++i) {
			scanf("%d %d", &x, &y);
			if(y > d) ok = 0;
			double offset = sqrt ( d * d - y * y );
			e[i].a = x - offset, e[i].b = x + offset;
			ava[i] = 1;
		}
		if(!ok) { printf("Case %d: -1\n", tc); continue; }
		sort(e, e + n);
		int stack[N], top = 0;
		stack[top++] = 0;
		for(i = 1; i < n; ++i) {
			while(top > 0 && dblcmp(e[stack[top-1]].b, e[i].b) != -1)  {
				ava[stack[--top]] = 0;
			}
			stack[top++] = i;
		}

		for(i = 0; !ava[i]; ++i);
		p[i] = e[i].b;
		int cnt = 1;
		for(i = i+1; i < n; ++i) if(ava[i]) {
			for(j = i-1; !ava[j]; j--);
			if(p[j] >= e[i].a)  p[i] = p[j];
			else { p[i] = e[i].b; cnt++; }
		}
		printf("Case %d: %d\n", tc, cnt);
	}
	return 0;
}


island222.cpp :

#include<iostream>
#include<cmath>
using namespace std;

const int MAX = 1003;
struct coordinate
{
	int x;
	int y;
}island[MAX];

struct a
{
	double left;
	double right;
}area[MAX];

/*
   按left升序排序 
 */
void Sorted(a* area)
{
	double left,right;
	for(int i=1;i<area[0].left;i++)
	{
		for(int j=1;j<=area[0].left-i;j++)
		{
			if (area[j].left - area[j+1].left > 0)
			{
				left = area[j].left;
				right = area[j].right;
				area[j].left = area[j+1].left;
				area[j].right = area[j+1].right;
				area[j+1].left = left; 
				area[j+1].right = right;
			} 
		}
	}
}

int Calculate(a* area)
{ 
	int count=1;
	double left = area[1].left;
	double right = area[1].right;
	for(int i=2;i<=area[0].left;i++)
	{
		if (area[i].left > right)
		{
			count++;  
			right = area[i].right;
		}
		else
		{
			if (area[i].right < right)
				right = area[i].right;
		}
	}
	return count;
}
int main()
{
	int n,d,dd,nCase;
	cin>>n>>d;
	nCase = 1;
	bool solution = true;

	while(n != 0 || d != 0)
	{
		island[0].x = n;//岛屿的个数 
		solution = true;
		for(int i=1;i<=n;i++)
		{
			cin>>island[i].x>>island[i].y;
			if (island[i].y > d)
				solution = false;
		}
		if (solution == false || n <= 0 || d <= 0)
			cout<<"Case "<<nCase<<": "<<-1<<endl;
		else
		{
			//算出每个岛可安雷达的最左边坐标和最右边坐标
			area[0].left = n;
			double a;
			dd = d*d;
			for(int j=1;j<=area[0].left;j++)
			{
				a =  sqrt(double(dd-island[j].y*island[j].y));
				area[j].left = island[j].x - a;
				area[j].right = island[j].x + a;
			} 
			Sorted(area); 
			cout<<"Case "<<nCase<<": "<<Calculate(area)<<endl;
		}
		cin>>n>>d;
		nCase++;

	}

	return 0;
}


我的WA程序。。。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXISLAND 1000
#define POW(a) (a)*(a)

struct xy {
	int x, y;
} xy[MAXISLAND];

int compare(const void *a, const void *b)
{
		return (*(struct xy *)a).x - (*(struct xy *)b).x;
}

int main()
{
	int island_n, radar_n, d, i, n = 0, no;
	double right_min, right;
	while (scanf("%d %d", &island_n, &d) != EOF && island_n) {
		n++, no = 0, radar_n = 0;

		if(d <= 0) {
			printf("Case %d: -1\n", n);
			break;
		}

		for (i = 0; i < island_n; i++)
			scanf("%d %d", &(xy[i].x), &(xy[i].y));
		scanf("\n");

		qsort(xy, island_n, sizeof(struct xy), compare);

		i = 0;
		while (i < island_n) {
			if (abs(xy[i].y) > d) {
				no = 1;
				printf("Case %d: -1\n", n);
				goto noo;
			}

			right_min = xy[i].x + sqrt(POW(d) - POW(xy[i].y));
			radar_n++;

			for (i++; i < island_n; i++) {
				if (abs(xy[i].y) > d) {
					no = 1;
					printf("Case %d: -1\n", n);
					goto noo;
				}
				if (xy[i].x - sqrt(POW(d) - POW(xy[i].y)) - right_min > 0.00001)
					break;
				right = xy[i].x + sqrt(POW(d) - POW(xy[i].y));
				right_min = right_min - right > 0.00001 ? right : right_min;
			}
		}

noo:	if (!no)
			printf("Case %d: %d\n", n, radar_n);
	}
}

• 貌似是啊，两个结果不一样，但是都AC了…… (0) ffxiangyu2 2009-04-23 20:33:16
• 我大概明白为什么了，不一样的数据有一个特点就是存在y<0，也就是说测试数据里应该没有y<0的情况 (0) ffxiangyu2 2009-04-23 21:57:49
  • Re:我大概明白为什么了，不一样的数据有一个特点就是存在y<0，也就是说测试数据里应该没有y<0的情况 (30) sanding 2009-04-30 20:06:28
• 是啊，我的也wa，不知为什么啊，下面是我的代码 (1039) jsmingzi 2009-07-18 20:25:55
  • Re:是啊，我的也wa，不知为什么啊，下面是我的代码 (11) 070220219 2009-08-10 15:20:04
• Re:通过此题，我对poj彻底绝望了…… (5670) xiaominzi 2009-08-22 09:41:30
  • Re:通过此题，我对poj彻底绝望了…… (0) king_k81 2009-08-27 20:10:52