POJ 1328 Radar Installation
https://vjudge.net/problem/POJ-1328
题目：
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
Examples
Input
3 2
1 2
-3 1
2 1 1 2
0 2 0 0
Output
Case 1: 2
Case 2: 1
分析：
写完AB之后发现真的不知道该怎么写C了。。。。几乎没什么坑现在还能踩了，于是又加一个A
题意很好理解，理解完之后直接干，用的二维贪心，，，
然后
mle。。。。Wawawa
从网上找的题解，都和我不同的思路？？？？
wtf？？？？
我的思路没毛病啊？？
然后自己又仔细用数学证明了一遍，发现如果两个同样很远的点就会出现问题，我的贪心策略会使得灯塔++
emmmmmmmmm那就只能重打一遍了
错误代码：
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
#define eps 1e-6
using namespace std;
struct A {
double x,y;
} a[];
int num = ;
int n;
double d;
int count0 = ;
bool cmp(A a, A b) {
if(a.x < b.x)
return true;
if(fabs(a.x - b.x) <= eps && a.y > b.y)
return true;
return false;
}
int f(int x) {
int xx = a[x].x + sqrt(d*d-a[x].y*a[x].y);
num ++;
for(int i = x+; i < n; i ++) { //p(i)
if(sqrt( a[i].y*a[i].y + (a[i].x-xx)*(a[i].x-xx) ) > d) {
f(i);
return ;
}
}
return ;
}
int main() {
while(~scanf("%d%lf",&n,&d) && (n != || d != 0.0)) {
num = ;
count0 ++;
int sta = ;
for(int i = ; i < n; i ++) {
slf(a[i].x) slf(a[i].y);
if(a[i].y > d) {
sta = ;
}
}
ps("Case ") p(count0) ps(": ");
if(sta == ) {
p(-) pn continue;
}
sort(a,a+n,cmp);
f();
p(num) pn
}
return ;
}
AC代码：
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <time.h>
#include <queue>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
#define LL long long
#define eps 1e-6
using namespace std;
struct A {
double l,r;
int sta ;
} a[];
int n;
double d;
int count0 = ;
int num = ;
int count1 = ;
bool cmp(A a, A b) {
if(a.r!=b.r)
return a.r<b.r;
return a.l>b.l;
return false;
} int f(int x) {
count1 ++;
for(int i = x+; i < n; i++) {
if(a[i].l > a[x].r) {
f(i);
return ;
}
}
return ;
} int main() {
while(~scanf("%d%lf",&n,&d) && (n != || d != 0.0)) {
num = ;
count0 ++;
count1 = ;
int sta = ;
double x,y;
for(int i = ; i < n; i ++) {
slf(x) slf(y);
if(y > d) {
sta = ;
}
a[i].l = x-sqrt(d*d-y*y);
a[i].r = x+ sqrt(d*d-y*y);
}
ps("Case ")
p(count0)
ps(": ");
if(sta == ) {
p(-) pn
continue;
}
sort(a,a+n,cmp);
//f(0);
double end=-0x3f3f3f3f;//横坐标要很小....因为..你懂的
for(int i=; i<n; i++) {
if(end<a[i].l) {
end=a[i].r;
count1++;
}
} p(count1) pn
} return ;
}