首页 > ACM题库 > HDU-杭电 > HDU 4173-Party Location-计算几何-[解题报告]HOJ
2015
05-23

HDU 4173-Party Location-计算几何-[解题报告]HOJ

Party Location

问题描述 :

After the programming contest, all of the contestants would like to throw a party. After the party, however, it will be late, and the contestants will be too tired to walk a long way home. In particular, each contestant refuses to come to the party if it is more than 2.5 km from his or her house.
The solution is to hold the party as close to as many of the contestants’ houses as possible. This is where you come in: your job is to determine the optimal location for the party, so that as many contestants as possible will be willing to attend it.

We consider the city to be a flat square, 50 km on each side. A contestant can walk directly from the party in a straight line to his or her house (there are no obstacles).

输入:

Input consists of a number of cases.
For each case, first there is a positive number N, which means the number of the contestants, and then N lines following, each line containing two floating point numbers indicating the (x,y) coordinates of the house of one of the contestants. Each coordinate is between 0.0 and 50.0 (km). Each house is at a distinct location. There are at most 200 contestants.

输出:

Input consists of a number of cases.
For each case, first there is a positive number N, which means the number of the contestants, and then N lines following, each line containing two floating point numbers indicating the (x,y) coordinates of the house of one of the contestants. Each coordinate is between 0.0 and 50.0 (km). Each house is at a distinct location. There are at most 200 contestants.

样例输入:

8
4.0 4.0
4.0 5.0
5.0 6.0
1.0 20.0
1.0 21.0
1.0 22.0
1.0 25.0
1.0 26.0

样例输出:

4

HDU 4173

题意:已知n(n<=200)位参赛选手的住所坐标,现要邀请尽可能多的选手来参加一个party,而每个选手对于离住所超过2.5Km的party一律不去,求最多可以有多少个选手去参加party。

思路:

不妨先考虑party可能的位置,要尽可能多的邀请到选手参加,则只需考虑party所在位置在某两位住所连线的中点上或某选手住所所在位置,因为这是最大参加party选手数很有可能在的位置。

若其他位置能得到最大参加选手数,那么中点或选手住所也一定可得到。//反证法可得,试着画画就ok~

那么,只要我们枚举所有中点与选手住所的位置,所能得到的可参加party选手数,取其最大值即是答案。

AC code:

/*
* @author Novicer
* language : C++/C
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;

const int maxn = 200 +5;
pair<double,double>con[maxn];

int main(){
//	freopen("input.txt","r",stdin);
	int n;
	while(cin >> n){
		for(int i = 1 ; i <= n ; i++) scanf("%lf%lf",&con[i].first,&con[i].second);
		int ans = 0;
		for(int i = 1 ; i <= n ; i++){
//			cout << con[i].first << " " << con[i].second << endl;
			for(int j = 1 ; j <= n ; j++){
				pair<double,double> t;
				t.first = (con[i].first + con[j].first) / 2.0;
				t.second = (con[i].second + con[j].second) / 2.0;
//				cout << t.first << " " << t.second << endl;
				int cnt = 0;
				for(int k = 1 ; k <= n ; k++){
					double dis = pow(t.first - con[k].first,2) + pow(t.second - con[k].second,2);
//					cout << dis << endl;
					if(dis <= 6.25 + eps) cnt++;
				}
				ans = max(ans , cnt);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

版权声明:博主表示授权一切转载啦,不过要写上原作者哦:)

参考:http://blog.csdn.net/qq_15714857/article/details/47060439