【2020年牛客暑假第二场】B题 Boundary

传送门：https://ac.nowcoder.com/acm/contest/5667/B

题意

题目描述 Given $n$ points in 2D plane. Considering all circles that the origin point$(0,0)$is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

输入描述： The first line contains one integer $n(1\leq n \leq 2000)$, denoting the number of given points. Following $n$ lines each contains two integers$x,y(x,y\leq10000)$,denoting a given point$(x,y)$. It’s guaranteed that the points are pairwise different and no given point is the origin point.

输出描述： Only one line containing one integer, denoting the answer.

输入 $4$ $1$ $1$ $0$ $2$ $2$ $2$ $2$ $2$

输出 $3$

思路

可知三点可得一个圆，所以利用三点求出该圆的圆心。 参考：http://www.skcircle.com/?id=642

因为原点是一定在圆上的，所以当我们确定一个圆心时，将该圆心用map保存下来，当另一组两个点加一个原点求出来的圆心还是该值，就可以知道这些求出来圆心相同的点都在同一个圆上，所以求出来之后$mmp[pdd(x0,y0)]++$ ,在和已经知道的圆上最大点数$cnt$比较，取较大者，最后输出时还要$cnt+1$，因为两个点确定一个圆心（原点没算了）。

我的错误： 在WA和T的道路上永垂不朽，求个数的时候太复杂了，导致心态炸裂.冷静下来还是可以想到的

错误Code

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
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
//const ll mod = 1e9 + 7;
// const int maxn = 1e5 + 10;

int n;
struct Mariex{
    double x, y;
    map<double, map<double, double>> tmp;
}a[2005];

map<double, map<double, double>> mp;

int cnt = 1;
int ans = 0;

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    for(int i = 1;i <= n; i++)
    {
        for(int j = i + 1;j <= n; j++)
        {
            double a1 = -0.5 * (a[i].x * a[i].x + a[i].y * a[i].y);
            double a2 = -0.5 * (a[j].x * a[j].x + a[j].y * a[j].y);
            double det = a[i].y * a[j].x - a[i].x * a[j].y;
            if(det == 0)
                continue;
            double x0 = 1.0 * (a[j].y * a1 - a[i].y * a2) / det;
            double y0 = 1.0 * (a[i].x * a2 - a[j].x * a1) / det;
            if(!a[i].tmp[x0][y0])
            {
                a[i].tmp[x0][y0] = 1;
                mp[x0][y0]++;
            }
            if(!a[j].tmp[x0][y0])
            {
                a[j].tmp[x0][y0] = 1;
                mp[x0][y0]++;
            }
            if(cnt < mp[x0][y0])
                cnt = mp[x0][y0];
            if(cnt > n / 2)
            {
                printf("%d",cnt);
                return ;
            }
        }
    }
    printf("%d",cnt);
}

signed main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    //ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

==主要是圆心算出来之后那一块时间T了，我哭了。==

正确Code

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
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<double, double> pdd;

##define INF 0x7f7f7f
##define mem(a,b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)
// const ll mod = 1e9 + 7;
// const int maxn = 1e5 + 10;
// const double eps = 1e-6;

int n;
struct Mariex{
    double x, y;
}a[2005];

map<pdd, int> mmp;

int cnt = 0;

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
    {
        scanf("%lf%lf",&a[i].x,&a[i].y); // 输入每点坐标
    }
    ll x1, x2, x3, y1, y2, y3; // 三点坐标
    ll A1, B1, C1, A2, B2, C2;
    double x0, y0;
    for(int i = 1;i <= n; i++)
    {
        mmp.clear();
        for(int j = i + 1;j <= n; j++)
        {
            x1 = y1 = 0;
            x2 = a[i].x; y2 = a[i].y;
            x3 = a[j].x; y3 = a[j].y;
            A1 = 2ll * (x2 - x1);
            B1 = 2ll * (y2 - y1);
            C1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
            A2 = 2ll * (x3 - x2);
            B2 = 2ll * (y3 - y2);
            C2 = x3 * x3 + y3 * y3 - x2 * x2 - y2 * y2;
            ll det = B2 * A1 - B1 * A2;
            if(det == 0) // 三点共线
                continue;
            x0 = 1.0 * (B2 * C1 - C2 * B1) / det;
            y0 = 1.0 * (A1 * C2 - A2 * C1) / det;
            cnt = max(cnt, ++mmp[pdd(x0, y0)]);
        }
    }
    printf("%d\n",cnt + 1);
}

signed main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
##else
    //ios::sync_with_stdio(false);
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/07/13/2020-nowcoder-shujia-2-b/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！