2015
05-23

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

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;
}