> 自己写的代码通过了自己的测试，却通不过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);
> 	}
> }

• Re:通过此题，我对poj彻底绝望了…… (0) king_k81 2009-08-27 20:10:52