传送门: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++) 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 () { ##ifdef FZT_ACM_LOCAL freopen ("in.txt" , "r" , stdin); freopen ("out.txt" , "w" , stdout); ##else int T = 1 ; 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++) 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 () { ##ifdef FZT_ACM_LOCAL freopen ("in.txt" , "r" , stdin); freopen ("out.txt" , "w" , stdout); ##else int T = 1 ; while (T--) solve (); ##endif return 0 ; }
本文作者:jujimeizuo 本文地址 : https://blog.jujimeizuo.cn/2020/07/13/2020-nowcoder-shujia-2-b/ 本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!