首页 > ACM题库 > HDU-杭电 > HDU 1077 Catching Fish-计算几何基础-[解题报告] C++
2013
11-27

HDU 1077 Catching Fish-计算几何基础-[解题报告] C++

Catching Fish

问题描述 :

Ignatius likes catching fish very much. He has a fishnet whose shape is a circle of radius one. Now he is about to use his fishnet to catch fish. All the fish are in the lake, and we assume all the fish will not move when Ignatius catching them. Now Ignatius wants to know how many fish he can catch by using his fishnet once. We assume that the fish can be regard as a point. So now the problem is how many points can be enclosed by a circle of radius one.Note: If a fish is just on the border of the fishnet, it is also caught by Ignatius.

输入:

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with a positive integer N(1<=N<=300) which indicate the number of fish in the lake. Then N lines follow. Each line contains two floating-point number X and Y (0.0<=X,Y<=10.0). You may assume no two fish will at the same point, and no two fish are closer than 0.0001, no two fish in a test case are approximately at a distance of 2.0. In other words, if the distance between the fish and the centre of the fishnet is smaller 1.0001, we say the fish is also caught.

输出:

For each test case, you should output the maximum number of fish Ignatius can catch by using his fishnet once.

样例输入:

4
3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210

样例输出:

2
5
5
11

比较简单的计算几何,首先枚举两个在圆上的点,然后数一数多少个点在此圆上,复杂度n^3。但是要注意的是如果这样得到的结果是0,那么还是要输出1,因为至少可以捞一条鱼,这是一个易错点!

/*
 * hdu1077/win.cpp
 * Created on: 2012-10-25
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 310;
const double eps = 1e-4;
typedef struct MyPoint {
    double x, y;
    MyPoint() {        x = y = 0;    }
    MyPoint(double xx, double yy) {        x = xx;        y = yy;    }
    MyPoint(const MyPoint &p1, const MyPoint &p2) {
        x = (p1.x + p2.x) / 2;
        y = (p1.y + p2.y) / 2;
    }
}MyPoint;
inline double mydistance(const MyPoint &p1, const MyPoint &p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
inline MyPoint operator-(const MyPoint &p1, const MyPoint &p2) {
    return MyPoint(p1.x - p2.x, p1.y - p2.y);
}
MyPoint points[MAXN];
int N, ans;

inline void getcenter(const MyPoint &p1, const MyPoint &p2, MyPoint &c) {
    MyPoint diff = p1 - p2;
    MyPoint mid(p1, p2);
    double angle;
    double high = mydistance(p1, p2) / 2;
    high = sqrt(1 - high * high);
    if (fabs(diff.x) < eps) {
        c.x = mid.x + high;
        c.y = mid.y;
    } else {
        angle = atan(diff.y / diff.x);
        c.x = mid.x - high * sin(angle);
        c.y = mid.y + high * cos(angle);
    }
}

inline bool myjudge(const MyPoint &p1, const MyPoint &p2) {
    double dis = mydistance(p1, p2);
    return dis <= 1 + eps;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in" , "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        for(int i = 0; i < N; i++) {
            scanf("%lf%lf", &points[i].x, &points[i].y);
        }
        ans = 1;
        MyPoint p;
        for(int i = 0; i < N; i++) {
            for(int j = i + 1; j < N; j++) {
                if(mydistance(points[i], points[j]) > 2 + eps + eps) {
                    continue;
                }
                getcenter(points[i], points[j], p);
                int t = 0;
                for(int k = 0; k < N; k++) {
                    if(myjudge(p, points[k])) {
                        t++;
                    }
                }
                if(t > ans) {
                    ans = t;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

  1. [email protected]

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