首页 > 代码库 > poj1328解题报告（贪心、线段交集）

poj1328解题报告（贪心、线段交集）

2024-07-06 20:23:02   228人阅读

 

POJ 1328，题目链接http://poj.org/problem?id=1328

题意：

有一海岸线（x轴），一半是陆地（y<0）、一半是海（y>0），海上有一些小岛（用坐标点表示P1、P2...），现要在海岸线上建雷达（覆盖半径R）。给出所有小岛的位置，和雷达半径，求最少需要多少个雷达？

 

思路：

1. 知道小岛位置，和雷达半径，那么以小岛为圆心，雷达覆盖半径为半径画圆，可以求出小岛与x轴有0（雷达无法覆盖）、1（雷达只能在这个点上才能覆盖）、2个交点（雷达在两点之间都能覆盖该小岛）

2. 要求最少雷达多少个，即把雷达放在1中线段的交集内。

那么这就变成了线段交集问题。（贪心）

代码：

?
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
//404k 79ms
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
 
typedef struct tagLINE{
    double left;
    double right;
}Line;
void sortLineBuf(Line *p, int num)
{
    Line temp;
    for (int i=0; i<num; ++i)
    {
        for (int j=i+1; j<num; ++j)
        {
            if (p[j].left < p[i].left){
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
}
int main()
{
    int caseNum = 0;
    double tempPoint;
    Line tempLine;
    while (true)
    {
        int islandNum = 0, r = 0;
        scanf("%d%d", &islandNum, &r);
        if (islandNum == 0 && r == 0) break;
 
        double *p = (double*)malloc(sizeof(double) * islandNum * 2);
        double *pX = p;
        double *pY = p+islandNum;
        for(int i=0; i<islandNum; ++i){
            scanf("%lf%lf", &pX[i], &pY[i]);
        }
        //
        int rapar = 0;
        bool bImpossible = true;
        Line* pLine = (Line*)malloc(sizeof(Line) * islandNum);
        //1 转换为直线
        for(int i=0; i<islandNum; ++i){
            if (fabs(pY[i]) > r){
                bImpossible = false;
                rapar = -1;
                break;
            }
            tempPoint = sqrt(r*r - pY[i]*pY[i]);
            pLine[i].left = pX[i]-tempPoint;
            pLine[i].right = pX[i]+tempPoint;
        }
        if (bImpossible)
        {
            rapar = 1;
            //2
            sortLineBuf(pLine, islandNum);
            //3 求解线段交集
            tempLine = pLine[0];
            for (int i=1; i<islandNum; ++i) 
            { 
                if (pLine[i].left > tempLine.right) 
                { 
                    ++rapar;
                    tempLine = pLine[i];
                } 
                else if (pLine[i].right < tempLine.right) 
                { 
                    tempLine = pLine[i]; 
                } 
            }
        }
        printf("Case %d: %d\n", ++caseNum, rapar);
        free(p);
        free(pLine);
    }
 
    return 0;
}

 

 

 

 


联系
我们