今天期末考试成绩出来了，在认认真真地看完自己的各科成绩、GPA、排名过后，心里只是有一种说不出来的无奈感，果然，这个学期还是个学渣么，看着镜子里的自己，感觉什么也说不出来，也没什么好说的，只能继续刷POJ，刷完了到点就去健身，然后回来晚饭，晚饭完了继续刷POJ，最后总算是把POJ1328 給AC了。
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 66695 | Accepted: 14946 |
Description
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
Sample Input
|
1 2 3 4 5 6 7 8 9 |
3 2 1 2 -3 1 2 1 1 2 0 2 0 0 |
Sample Output
|
1 2 |
Case 1: 2 Case 2: 1 |
Source
这道题目的关键之处就是把面的问题转换成线的问题，每一个座海岛在x轴上有一个区间，在这个区间里面的雷达都可以侦测到海岛，区间的范围即是[x-sqrt(dd – yy), x+sqrt(dd+yy)]，然后先以右端点为基进行从小到大排序，然后把第一个雷达默认放在最左端的xmax，接下来的点只要是xmin小于当前xmax就可以不用增加雷达，如果xmax == xmin的话也不用增加雷达。然后如果xmax < xmin的话就加一个雷达，然后以xmin所属区间的xmax为基进行比较。
其实一开始用链表写了一个一百多行的，结果折腾来折腾去也是各种WA，RE，TLE什么的，然后江老师看了我之前代码里面那么大的一段冒泡排序过后就果断说代码时间复杂度高了，建议试一试用STL里面的sort函数，后来上网七摸八摸再请教了江老师一下，就用STL重新写了个，代码速度提了不少不说，还精简了不少，虽然还没有仔细研究，但是已经感觉到了STL果断神器，必须好好搞一搞了。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
/************************************************************************* > File Name: poj1328.cpp > Author: razrLeLe > Personal homepage: https://yueyu.io > Created Time: Wed 09 Jul 2014 01:25:29 PM CST ************************************************************************/ #include <iostream> using namespace std; #include <algorithm> #include <cmath> typedef struct flag { int n; flag *next; }*Flag; struct Range { double xmin, xmax; }; bool cmp(const Range &a, const Range &b) { return a.xmax < b.xmax; //只对右区间进行排序 } int calculate(const int n,const double d) { double x, y; int flag = 0;//专门有一个flag用来标记是否存在y > d的情况，不能直接中断输入 Range xm[1000]; if(n > 1000) return -1; for(int i = 0; i < n; i++) { cin >> x >> y; if(y > d) flag = -1; xm[i].xmin = x - sqrt(d*d - y*y); xm[i].xmax = x + sqrt(d*d - y*y); } if(flag == -1) return -1; sort(xm, xm+n, cmp); int count = 1; double buffer = xm[0].xmax; for(int i = 0; i < n; i++) { if(buffer < xm[i].xmin) { count++; buffer = xm[i].xmax; } } return count; } int main() { int n; double d; int num = 1; Flag L, p, q; L = new flag; p = L; while(cin >> n >> d) { if(n == 0 && d == 0) break; q = new flag; q->next = NULL; p->next = q; p = p->next; p->n = calculate(n, d); num++; } p = L->next; for(int i = 1; i < num; i++) { cout << "Case " << i << ": " << p->n << endl; p = p->next; } return 0; } |
附上测试数据一组，来自poj Discuss：
2 5
-3 4
-6 3
4 5
-5 3
-3 5
2 3
3 3
20 8
-20 7
-18 6
-5 8
-21 8
-15 7
-17 5
-1 5
-2 3
-9 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 7
9 6
10 5
0 0
2 3
0 2
2 3
2 3
0 2
1 3
3 3
1 2
-3 2
2 4
8 5
2 4
-4 4
-3 3
-3 1
-3 0
-1 0
0 5
6 0
3 0
1 2
-3 1
2 1
3 2
1 2
-3 1
2 1
1 2
0 2
2 3
0 2
2 3
4 -5
4 3
4 3
2 3
6 -9
3 -3
1 2
-3 2
2 1
6 2
1 2
1 2
1 2
-3 1
2 1
0 0
1 2
0 2
2 3
0 2
1 3
3 10
1 10
2 3
4 5
3 5
1 10
2 3
4 5
4 7
1 10
2 3
4 5
0 0
3 9
1 10
2 3
4 5
0 0
================结果
Case 1: 1
Case 2: 2
Case 3: 4
Case 4: 1
Case 5: 1
Case 6: -1
Case 7: 3
Case 8: -1
Case 9: 2
Case 10: 1
Case 11: 1
Case 12: -1
Case 13: -1
Case 14: 2
Case 15: 1
Case 16: 1
Case 17: 1
Case 18: -1
Case 19: -1
Case 20: -1
挥着翅膀的鳖 献上。。。
d<=0不需要判断
y<=0 不需要判断
把每个岛屿来当做雷达的圆心，半径为d，做圆，与x轴会产生两个焦点L和R，这就是一个区间；
首先就是要把所有的区间找出来，然后x轴从左往右按L排序，再然后就是所谓的贪心把那些互相重叠的区间去掉就行了，
晚上AC了过后，感觉心里面其实也没什么难过不难过的，只能说是稍微有一点郁闷吧，接下来继续high就是了～