HDOJ 1077 Catching Fish

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1077

很不错的一道题目。

方法是:数学+贪心+暴力

思路:

从所有点中依次取两点,然后判断到两点m, n距离为半径1的点centre(易知center在m, n连线的中垂线上)。然后判断其余有多少点在以centre为圆心的圆内,记作ans,最后找出最大的ans,就是要求的值。

不过代码不是很好理解,我作了图,把重要的地方用图来解释。

以下是AC代码:

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
// Author: Tanky Woo
// Blog:     www.WuTianQi.com
#include <iostream>
#include <cmath>
using namespace std;
 
int nCases, nPoints;
 
typedef struct Point{
    double x, y;
}Point;
 
Point point[305];
 
double dis(Point m, Point n)
{
    Point p;
    p.x = m.x - n.x;
    p.y = m.y - n.y;
    return p.x*p.x + p.y*p.y;
}
 
// 找出距离m, n两点长为1的点
// 也就是两点连线中垂线上的一点。
Point FindCentre(Point m, Point n)
{
    Point p, mid, centre;
    double di2, gao;   // 直角三角形的底的平方和高,斜边为1
    double jiao;       // 斜边与底边的夹角
    p.x = m.x - n.x;
    p.y = m.y - n.y;
    mid.x = (m.x + n.x)/2;
    mid.y = (m.y + n.y)/2;
    di2 = dis(mid, m);
    gao = sqrt(1 - di2);
    if(fabs(p.y) < 1e-6)    // m, n两点在垂直于x轴的同一垂线上
    {
        centre.x = mid.x;
        centre.y = mid.y + gao;
    }
    else
    {
        jiao = atan(-p.x/p.y);   // 这里我画图讲解
        centre.x = mid.x + gao*cos(jiao);
        centre.y = mid.y + gao*sin(jiao);
    }
    return centre;
}
 
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int ans, tmpans;
    double tmp;
    Point centre;
    scanf("%d", &nCases);
    while(nCases--)
    {
        ans = 1;
        scanf("%d", &nPoints);
        for(int i=0; i<nPoints; ++i)
            scanf("%lf %lf", &point[i].x, &point[i].y);
        for(int i=0; i<nPoints; ++i)
            for(int j=i+1; j<nPoints; ++j)
            {
                if(dis(point[i], point[j]) > 4)
                    continue;
                tmpans = 0;
                centre = FindCentre(point[i], point[j]);
                for(int k = 0; k < nPoints; ++k)
                {
                    tmp = dis(centre, point[k]);
                    if(tmp <= 1.000001) tmpans++;
                }
                if(ans < tmpans) 
                    ans = tmpans;
            }
        printf("%d\n", ans);        
    }
    return 0;
}

 

这个是FindCentre的图:

 

 由图可以看到。FindCentre的

di(即直角三角形的底边)是m到mid的值, gao(即直角三角形的高)是centre到mid的值,centre就是到m, n两点距离为1的点,FindCentre的主要部分就是求centre的坐标。可以通过mid点加上偏移的x和y。

而偏移的x, y由jiao(即角度)求出,tan(jiao) = x/y,图中两个角的转换我已经画出,根据初中直角三角形知识知道两个角相等,即可求出偏移的x和y。

POJ 2524 Ubiquitous Religions

题目地址:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2524


题意:
已知有n个大学生,其中有m对宗教信仰相同的学生,请你估算这n个学生中最多有多少种宗教信仰。

还是并查集~~~不在同一个几何里的合并,并把集合数N减一。求最后的N值。

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
#include <iostream>
using namespace std;
 
#define MAX 500001
 
// father[x]表示x的父节点
int father[MAX];
// rank[x]表示x的秩
int rank[MAX];
 
// 初始化
void Make_Set(int n)
{
	for(int i=1; i<=n; ++i)
	{
		father[i] = i;
		rank[i] = 0;
	}
}
 
// 查找
int Find_Set(int x)
{
	if(x != father[x])
		return Find_Set(father[x]);
	return x;
}
 
// 合并
void Union(int x, int y)
{
	x = Find_Set(x);
	y = Find_Set(y);
	if(x == y)  // x,y在同一个集合
		return;
	if(rank[x] > rank[y])
		father[y] = x;
	else if(rank[x] < rank[y])
		father[x] = y;
	else
	{
		rank[y]++;
		father[x] = y;
	}
}
 
int main()
{
	int N, M, a, b;
	int nCases = 1;
	while(scanf("%d %d", &N, &M) && (M||N))
	{
		Make_Set(N);
		for(int i=1; i<=M; ++i)
		{
			scanf("%d %d", &a, &b);
			a = Find_Set(a);
			b = Find_Set(b);
			//如果a,b不在同一个集合,则合并
			if(a != b)
			{
				N--;
				Union(a, b);
			}
		}
		printf("Case %d: %d\n", nCases++, N);
	}
	return 0;
}

HDOJ 1232 畅通工程

题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1232


经典的并查集应用~~~直接套模版就行了。
思路,找到小镇的father值等于自己的个数,减去1就是还要修的路。Orz

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
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <assert.h>
#include <algorithm>
using namespace std;
 
#define MAX 1005
/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX]; 
 
/* 初始化集合 */
void Make_Set(int x)
{
        father[x] = x;
        rank[x] = 0;
} 
 
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
 
        if(x != father[x])
        {
                father[x] = Find_Set(father[x]);
        }
        return father[x];
} 
 
/* 按秩合并x,y所在的集合 */
void Union(int x, int y)
{
        x = Find_Set(x);
        y = Find_Set(y);
        if (x == y) return;
        if (rank[x] > rank[y])
        {
                father[y] = x;
        }
        else
        {
                if (rank[x] == rank[y])
                {
                        rank[y]++;
                }
                father[x] = y;
        }
} 
int N, M;
int main()
{
    int a, b;
    while(scanf("%d", &N) && N)
    {
        for(int i=1; i<=N; ++i)
            Make_Set(i);
        scanf("%d", &M);
        while(M--)
        {
            scanf("%d %d", &a, &b);
            Union(a, b);
        }
        int cnt = -1;
        for(int i=1; i<=N; ++i)
            if(father[i]==i)
                cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}