#include stdio.h #include math.h #include malloc.h struct location { double x; double y; bool processed; }; struct locationValidXRange { double begin; double end; }; bool locationCanReach(location * islandLocation, int islandNum, double rad
#include <stdio.h>
#include <math.h>
#include <malloc.h>
struct location {
double x;
double y;
bool processed;
};
struct locationValidXRange {
double begin;
double end;
};
bool locationCanReach(location * islandLocation, int islandNum, double radarDistance) {
for (int i = 0; i < islandNum; i++) {
if (islandLocation[i].y > radarDistance) {
return false;
}
}
return true;
}
void swapLoctaionRange(locationValidXRange * locationRange1, locationValidXRange * locationRange2) {
double begin = locationRange1->begin;
double end = locationRange1->end;
// bool processed = location1->processed;
locationRange1->begin = locationRange2->begin;
locationRange1->end = locationRange2->end;
// location1->processed = location2->processed;
locationRange2->begin = begin;
locationRange2->end = end;
// location2->processed = processed;
}
void sortLocationsRangeAsBeginAscend(locationValidXRange * islandLocationRange, int islandNum) {
for (int i = 0; i < islandNum - 1; i++) {
bool exchanged = false;
for (int j = 0; j <= (islandNum - i) -1 - 1; j++) {
if (islandLocationRange[j].begin > islandLocationRange[j+1].begin) {
swapLoctaionRange(islandLocationRange + j, islandLocationRange + j + 1);
exchanged = true;
}
}
if (!exchanged) {
return;
}
}
}
double getMaxXForLocation(location * islandLocation, double radarDistance) {
double sqrtRes = sqrt((double)radarDistance*radarDistance - islandLocation->y * islandLocation->y);
return sqrtRes + islandLocation->x;
}
void getValidXRangeForLocation(location * islandLocation, double radarDistance, double *begin, double *end) {
double sqrtRes = sqrt((double)radarDistance*radarDistance - islandLocation->y * islandLocation->y);
*begin = ((double)islandLocation->x - sqrtRes);
*end = ((double)islandLocation->x + sqrtRes);
}
int getRadarMinNum(locationValidXRange * islandLocationRanges, int rangeNum) {
int radarNum = 1;
double begin = islandLocationRanges[0].begin;
double end = islandLocationRanges[0].end;
for(int i = 1; i < rangeNum ;i++) {
if (islandLocationRanges[i].begin <= end) {
begin = islandLocationRanges[i].begin;
end = end > islandLocationRanges[i].end ? islandLocationRanges[i].end : end;
} else {
radarNum++;
begin = islandLocationRanges[i].begin;
end = islandLocationRanges[i].end;
}
}
return radarNum;
}
void printLocationRanges(locationValidXRange * islandLocationRanges, int islandNum) {
printf("=========================================\n");
for (int i = 0; i < islandNum ; i++) {
printf("%lf %lf\n", (islandLocationRanges+i)->begin, (islandLocationRanges+i)->end);
}
printf("=========================================\n");
}
int main() {
int caseId = 1;
while(1) {
int islandNum;
double radarDistance;
scanf("%d %lf\n", &islandNum, &radarDistance);
if (islandNum == 0 && radarDistance == 0) {
return 0;
}
location * islandLocations = (location *) malloc(islandNum * sizeof(location));
locationValidXRange * locationValidXRanges = (locationValidXRange *) malloc(islandNum * sizeof(locationValidXRange));
for (int i = 0; i < islandNum ; i++) {
scanf("%lf %lf", &(islandLocations[i].x), &(islandLocations[i].y));
getValidXRangeForLocation(islandLocations + i, radarDistance, &(locationValidXRanges[i].begin), &(locationValidXRanges[i].end));
islandLocations[i].processed = false;
}
if (!locationCanReach(islandLocations, islandNum, radarDistance)) {
printf("Case %d: -1\n", caseId);
caseId++;
continue;
}
sortLocationsRangeAsBeginAscend(locationValidXRanges, islandNum);
// printLocationRanges(locationValidXRanges, islandNum);
printf("Case %d: %d\n", caseId, getRadarMinNum(locationValidXRanges, islandNum));
free((void*)islandLocations);
islandLocations = NULL;
caseId++;
}
}
贪心法： 每次的radar都以能覆盖最多的小岛为选择准则（证明可以用算法导论的替代法则： 假如当前的一个最优解里不是当前选择的radar位置，
那么置换成贪心法的选择，则结果只会更好，不会更差。）
先用radar的半径求出所有小岛的x range（radar在此range可以覆盖小岛）， 然后以range begin做升序排序，最后便利一边range数组，
每次更新当前的有效range，如果当前range不能覆盖此小岛，则radar数量+1， range刷新为此小岛的range。
一开始用贪心法没找对对象，用每次能覆盖第一的小岛的x坐标最大的radar作为标准，是不对。
贪心和动规难就在于找出这种最优子结构。
注意：
1. 小岛的坐标， radar的坐标， 半径都要用double，不然WA。
2. 一开始接收输入时，就可以判断小岛的y坐标，超过了radar半径，直接返回-1.
3. double 用 %lf。
4 struct封装很方便。 感受了封装性的内涵.
5. malloc free -> malloc.h