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

题目链接：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.

输入描述：
The first line contains one integer $n(1\leq n \leq 2000)$n(1≤n≤2000), denoting the number of given points.
Following $n$n lines each contains two integers$x,y(|x|,|y|\leq10000)$x,y(∣x∣,∣y∣≤10000),denoting a given point$(x,y)$(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$4
$1$1 $1$1
$0$0 $2$2
$2$2 $2$2
$2$2 $2$2

输出
$3$3

思路

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

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

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

错误Code

#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

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