Highway

Highway

Bob is a skilled engineer. He must design a highway that crosses a region with few villages. Since this region is quite unpopulated, he wants to minimize the number of exits from the highway. He models the highway as a line segment S (starting from zero), the villages as points on a plane, and the exits as points on S. Considering that the highway and the villages position are known, Bob must find the minimum number of exists such that each village location is at most at the distance D from at least one exit. He knows that all village locations are at most at the distance D from S.

The program input is from a text file. Each data set in the file stands for a particular set of a highway and the positions of the villages. The data set starts with the length L (fits an integer) of the highway. Follows the distance D (fits an integer), the number N of villages, and for each village the location (x,y). The program prints the minimum number of exits.White spaces can occur freely in the input. The input data are correct and terminate with an end of file.

For each set of data the program prints the result to the standard output from the beginning of a line. An input/output sample is in the table below. There is a single data set. The highway length L is 100, the distance D is 50. There are 3 villages having the locations (2, 4), (50, 10), (70, 30). The result for the data set is the minimum number of exits: 1.

100
50
3
2 4
50 10
70 30

1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 10005

struct SEG
{
double b, e;
};

int cmp(const void *p1, const void *p2)
{
if(((struct SEG*)p1)->b != ((struct SEG*)p2)->b)
return ((struct SEG*)p1)->b - ((struct SEG*)p2)->b;
else
return ((struct SEG*)p1)->e - ((struct SEG*)p2)->e;
}
int main()
{
int n;
double d, l;
while(scanf("%lf%lf%d", &l, &d, &n) != EOF)
{
struct SEG S[N];
int i, ans = 1;
double d2 = d * d, r,x,y;
double cr;
for (i = 0; i < n; i++)
{
scanf("%lf%lf", &x, &y);
r = sqrt(d2 - y*y);
S[i].b = x-r, S[i].e = x+r;     /* 每个 village 在x轴上的允许范围  */
}
//sort(S, S + n, cmp);
qsort(S,n,sizeof(struct SEG),cmp);
cr = S.e;        /*  当前区间端点位置 */
for(i = 1; i < n; i++)
{
if(S[i].b > cr)         /* 下一个区间与当前区间不相交 */
cr = S[i].e, ans++;
else if(cr > S[i].e)    /* 下一个区间被当前区间包含，更新当前区间端点位置 */
cr = S[i].e;
}
printf("%d\n", ans);
}
return 0;
}

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 10005
int n;
double d, l;
struct SEG
{
double b, e;
};
SEG S[N];
int cmp(const SEG &p1, const SEG &p2)
{
if(p1.b != p2.b) return p1.b < p2.b;
else return p1.e < p2.e;
}
int solve()
{
int i, ans = 1;
double d2 = d * d, r,x,y;
for (i = 0; i < n; i++)
{
scanf("%lf%lf", &x, &y);
r = sqrt(d2 - y*y);
S[i].b = x-r, S[i].e = x+r;

}
sort(S, S + n, cmp);
double cr = S.e;
for(i = 1; i < n; i++)
{
if(S[i].b > cr)
cr = S[i].e, ans++;
else if(cr > S[i].e)
cr = S[i].e;
}
return ans;

}
int main()
{
while(scanf("%lf%lf%d", &l, &d, &n) != EOF)
printf("%d\n", solve());
return 0;
}