欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2020牛客暑期多校训练营(第二场)B-Boundary

程序员文章站 2022-05-12 12:28:25
...

题目链接:
https://ac.nowcoder.com/acm/contest/5667/B
Given {n}n points in 2D plane. Considering all circles that the origin point {(0, 0)}(0,0) is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

题意:给你若干个点,找一个过原点的圆使圆上经过的点最多。
思路:因为数据范围给的1e3,所以可以n^2地跑。由于三点确定一个圆,有一个点又是知道的(0,0),那可以枚举其余每对点。找到他们分别与原点的中垂线的交点,continue掉中垂线平行的情况
2020牛客暑期多校训练营(第二场)B-Boundary

比赛结束前6分钟才意识到map是log(n)的。。。此时已经WT了15发了。

正确处理:看了dl代码恍然大悟。可以用一个数组先把所有的点存下来,sort一下,连续出现一样的就是那个位置的统计次数。得到最大次数之后,由于是所有的点里面两两取的,出现了重复。枚举答案,计算谁的组合数是maxm,即为所求。

关于中垂线交点如何算比较方便,某考研选手建议解方程组用克拉默法则。
2020牛客暑期多校训练营(第二场)B-Boundary

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 100;
const int mod = 998244353;

vector<pair<int, int> > p;
vector<pair<double, double> > cur;

ll getD(ll a11, ll a12, ll a21, ll a22) {
    return a11 * a22 - a12 * a21;
}

int main() {
   //ios::sync_with_stdio(0);
    int n;
    p.resize(2005);
    scanf("%d", &n);
    int x, y;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        p[i] = make_pair(x, y);
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            int x1 = p[i].first, y1 = p[i].second, x2 = p[j].first, y2 = p[j].second;
            ll a11 = 2 * x1, a12 = 2 * y1, a13 = x1 * x1 + y1 * y1;
            ll a21 = 2 * x2, a22 = 2 * y2, a23 = x2 * x2 + y2 * y2;
            ll D = getD(a11, a12, a21, a22);
            
            if (D == 0) {
                continue;
            }
            ll D1 = getD(a13, a12, a23, a22);
            ll D2 = getD(a11, a13, a21, a23);

            cur.push_back(make_pair((double)D1 / D, (double)D2 / D));
        }
    }

    sort(cur.begin(), cur.end());
    int mx = 0;
    for (int i = 0; i < cur.size(); ) {
        int j = i;
        while (j < cur.size() && cur[i] == cur[j]) j++;
        mx = max(mx, j - i);
        i = j;
    }
    int ans = 0;
    for (int u = 1; u < 5005; u++)
        if (u * (u - 1) / 2 <= mx)
            ans = max(ans, u);

    printf("%d\n", ans);

    return 0;
}

相关标签: ACM 算法