【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 协议。转载请注明出处!