POJ 1328 Radar Installation 贪心 A

POJ 1328 Radar Installation

题目：

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.
The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Examples

Input

Output

Case 1: 2
Case 2: 1

分析：

写完AB之后发现真的不知道该怎么写C了。。。。几乎没什么坑现在还能踩了，于是又加一个A
题意很好理解，理解完之后直接干，用的二维贪心，，，
然后

mle。。。。Wawawa
从网上找的题解，都和我不同的思路？？？？
wtf？？？？
我的思路没毛病啊？？
然后自己又仔细用数学证明了一遍，发现如果两个同样很远的点就会出现问题，我的贪心策略会使得灯塔++
emmmmmmmmm那就只能重打一遍了

错误代码：

 1 #include <stdio.h>  2 #include <math.h>  3 #include <string.h>  4 #include <algorithm>  5 #include <iostream>  6 #include <string>  7 #include <time.h>  8 #include <queue>  9 #include <string.h> 10 #define sf scanf 11 #define pf printf 12 #define lf double 13 #define ll long long 14 #define p123 printf("123\n"); 15 #define pn printf("\n"); 16 #define pk printf(" "); 17 #define p(n) printf("%d",n); 18 #define pln(n) printf("%d\n",n); 19 #define s(n) scanf("%d",&n); 20 #define ss(n) scanf("%s",n); 21 #define ps(n) printf("%s",n); 22 #define sld(n) scanf("%lld",&n); 23 #define pld(n) printf("%lld",n); 24 #define slf(n) scanf("%lf",&n); 25 #define plf(n) printf("%lf",n); 26 #define sc(n) scanf("%c",&n); 27 #define pc(n) printf("%c",n); 28 #define gc getchar(); 29 #define re(n,a) memset(n,a,sizeof(n)); 30 #define len(a) strlen(a) 31 #define LL long long 32 #define eps 1e-6 33 using namespace std; 34 struct A { 35 double x,y; 36 } a[100000]; 37 int num = 0; 38 int n; 39 double d; 40 int count0 = 0; 41 bool cmp(A a, A b) { 42 if(a.x < b.x) 43 return true; 44 if(fabs(a.x - b.x) <= eps && a.y > b.y) 45 return true; 46 return false; 47 } 48 int f(int x) { 49 int xx = a[x].x + sqrt(d*d-a[x].y*a[x].y); 50 num ++; 51 for(int i = x+1; i < n; i ++) { //p(i) 52 if(sqrt( a[i].y*a[i].y + (a[i].x-xx)*(a[i].x-xx) ) > d) { 53  f(i); 54 return 0; 55  } 56  } 57 return 0; 58 } 59 int main() { 60 while(~scanf("%d%lf",&n,&d) && (n != 0 || d != 0.0)) { 61 num = 0; 62 count0 ++; 63 int sta = 0; 64 for(int i = 0; i < n; i ++) { 65  slf(a[i].x) slf(a[i].y); 66 if(a[i].y > d) { 67 sta = 1; 68  } 69  } 70 ps("Case ") p(count0) ps(": "); 71 if(sta == 1) { 72 p(-1) pn continue; 73  } 74 sort(a,a+n,cmp); 75 f(0); 76  p(num) pn 77  } 78 return 0; 79 }

AC代码：

 1 #include <stdio.h>  2 #include <math.h>  3 #include <string.h>  4 #include <algorithm>  5 #include <iostream>  6 #include <string>  7 #include <time.h>  8 #include <queue>  9 #include <string.h> 10 #define sf scanf 11 #define pf printf 12 #define lf double 13 #define ll long long 14 #define p123 printf("123\n"); 15 #define pn printf("\n"); 16 #define pk printf(" "); 17 #define p(n) printf("%d",n); 18 #define pln(n) printf("%d\n",n); 19 #define s(n) scanf("%d",&n); 20 #define ss(n) scanf("%s",n); 21 #define ps(n) printf("%s",n); 22 #define sld(n) scanf("%lld",&n); 23 #define pld(n) printf("%lld",n); 24 #define slf(n) scanf("%lf",&n); 25 #define plf(n) printf("%lf",n); 26 #define sc(n) scanf("%c",&n); 27 #define pc(n) printf("%c",n); 28 #define gc getchar(); 29 #define re(n,a) memset(n,a,sizeof(n)); 30 #define len(a) strlen(a) 31 #define LL long long 32 #define eps 1e-6 33 using namespace std; 34 struct A { 35 double l,r; 36 int sta ; 37 } a[10000]; 38 int n; 39 double d; 40 int count0 = 0; 41 int num = 0; 42 int count1 = 0; 43 bool cmp(A a, A b) { 44 if(a.r!=b.r) 45 return a.r<b.r; 46 return a.l>b.l; 47 return false; 48 } 49 50 int f(int x) { 51 count1 ++; 52 for(int i = x+1; i < n; i++) { 53 if(a[i].l > a[x].r) { 54  f(i); 55 return 0; 56  } 57  } 58 return 0; 59 } 60 61 int main() { 62 while(~scanf("%d%lf",&n,&d) && (n != 0 || d != 0.0)) { 63 num = 0; 64 count0 ++; 65 count1 = 0; 66 int sta = 0; 67 double x,y; 68 for(int i = 0; i < n; i ++) { 69  slf(x) slf(y); 70 if(y > d) { 71 sta = 1; 72  } 73 a[i].l = x-sqrt(d*d-y*y); 74 a[i].r = x+ sqrt(d*d-y*y); 75  } 76 ps("Case ") 77  p(count0) 78 ps(": "); 79 if(sta == 1) { 80 p(-1) pn 81 continue; 82  } 83 sort(a,a+n,cmp); 84 //f(0); 85 double end=-0x3f3f3f3f;//横坐标要很小....因为..你懂的 86 for(int i=0; i<n; i++) { 87 if(end<a[i].l) { 88 end=a[i].r; 89 count1++; 90  } 91  } 92 93  p(count1) pn 94  } 95 96 97 return 0; 98 }