首页 > ACM题库 > HDU-杭电 > hdu 1922 Subway planning-贪心-[解题报告]C++
2013
12-25

hdu 1922 Subway planning-贪心-[解题报告]C++

Subway planning

问题描述 :

The government in a foreign country is looking into the possibility of establishing a subway system in its capital. Because of practical reasons, they would like each subway line to start at the central station and then go in a straight line in some angle as far as necessary. You have been hired to investigate whether such an approach is feasible. Given the coordinates of important places in the city as well as the maximum distance these places can be from a subway station (possibly the central station, which is already built), your job is to calculate the minimum number of subway lines needed. You may assume that any number of subway stations can be
built along a subway line.

Figure 1: The figure above corresponds to the first data set in the example input.

输入:

The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed
between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set
will be distinct (and none will be 0, 0).

输出:

The first line in the input file contains an integer N, the number of data sets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0 <= d < 150). n is the number of important places in the city that must have a subway station nearby, and d is the maximum distance allowed
between an important place and a subway station. Then comes n lines, each line containing two integers x and y (-100 <= x, y <= 100), the coordinates of an important place in the capital. The central station will always have coordinates 0, 0. All pairs of coordinates within a data set
will be distinct (and none will be 0, 0).

样例输入:

2
7 1
-1 -4
-3 1
-3 -1
2 3
2 4
2 -2
6 -2
4 0
0 4
-12 18
0 27
-34 51

样例输出:

4
2

Problem Address:http://acm.hdu.edu.cn/showproblem.php?pid=1922

【前言】

xlj问我有没有题做,没有的话给我一道。

我说我正在做,等一下。

然后敲完了一道离散的题,然后接过了这道题。

想了段时间之后找到了做法。

发现xlj的想法也是一样。

于是开始敲。谁知道这才是悲剧的开始。

敲好后debug过了sample,交之后狂WA。

hdu1922这道题只有几个人过了这道题,解题报告也找不到。

然后各种能考虑的情况都考虑进去,还是WA。

最后找到了解题报告,发现原来是poj3004。

做法也是一样的思路。

但还是WA。

前前后后在HDU上交了二十多次,在poj上交了几次。

xlj回来后继续,但是sample还没过。

后来发现他里面错漏百出。然后就改啊改。

但我的还是WA。

找到一份代码对照之后还是WA。

回宿舍后又提交了十几二十次,还是WA。

终于,在临近十二点的时候,发现了错误。

第一处错误是少写了一个字母,后来发现的时候,

虽然改过来了,但是下面又改错了。

于是华丽丽地傻×了。

如果没有那处错误的话,应该早就过了。

所以,这道题虽然出的很好,是神题,但并不是真的神了,而是我傻了……

【思路】

首先,如果某个点可以覆盖到原点,则把那个点直接去掉。

对于每个点,找出它的极角范围。从原点引该点半径为d的圆的两条切线,然后计算出切线的两个极角。

每个点都有两个极角,变成了贪心的区间覆盖问题。

要求自定义的区间个数,使所有的已知区间都包含这些区间,要使区间个数最小。

由于是圆环,所以扫描每个点,以该点作为断点,然后贪心一遍,取它们的最小值。

【代码】

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

#define min(a,b) ((a)<=(b)?(a):(b))

const int maxn = 1000;
const double pi = acos(-1.0);

struct point
{
    double x, y;
    double l, r;
}pt[maxn*2+1];

bool cmp(const point &a, const point &b)
{
    return a.l<b.l;
}

void set(point &p, double d, double dis)
{
    double a, b;
    if (p.x==0)
    {
        if (p.y>0) a = 0.5*pi;
        else a = 1.5*pi;
    }
    else if (p.y==0)
    {
        if (p.x>0) a = 0;
        else a = pi;
    }
    else
    {
        a = asin(fabs(p.y*1.0)/dis);
        if (p.x<0 && p.y>=0) a = pi - a;
        else if (p.x<=0 && p.y<0) a += pi;
        else if (p.x>0 && p.y<=0) a = 2*pi-a;
    }
    b = asin(1.0*d/dis);
    p.l = a-b;
    p.r = a+b;
}

double dist(double x, double y)
{
	return sqrt(x*x+y*y);
}

int main()
{
    int t;
    int n;
    double d;
    int i, j;
    int ct;
	double d1;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %lf", &n, &d);
        for (i=0; i<n; i++)
        {
            scanf("%lf %lf", &pt[i].x, &pt[i].y);
			d1 = dist(pt[i].x, pt[i].y);
			if (d1<=d)
			{
				i--;
				n--;
			}
			else set(pt[i], d, d1);
        }
        sort(pt, pt+n, cmp);
		for (i=n; i<2*n; i++)
		{
			pt[i].l = pt[i-n].l+2*pi;
			pt[i].r = pt[i-n].r+2*pi;
		}
		int ans = 1000000;
		for (j=0; j<n; j++)
		{
			ct = 1;
			double s = pt[j].r;
			for (i=1+j; i<n+j; i++)
			{
				if (s<pt[i].l)
				{
					ct++;
					s = pt[i].r;
				}
				else
				{
					s = min(s, pt[i].r);
				}
			}
			ans = min(ans, ct);
		}
		if (ans==1000000) ans = 0;
		printf("%d\n", ans);
    }
    return 0;
}

解题转自:http://blog.csdn.net/human_ck/article/details/6969564


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3