2020牛客暑期多校训练营（第二场）B.Boundary

题目链接

题目描述

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| \leq 10000)$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.

示例1

输入

4
1 1
0 2
2 0
2 2

输出

3

题解做法，看网上大多数人都是套圆心角公式的，我补一个题解做法：

题解很容易懂，做起来很容易错????
1.判断角度的个数不能直接用 $map$map，会有精度问题，只能过 65%
2.如果存每一个角度判断还是有精度问题，此时离成功只差一步之遥了，能过 90%，那就是必须要 $1e^{-10}$1e−10 的精度
求角度直接套的板子，判断向量的方向直接用叉积即可，AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
double ang[N*N],eps=1e-10;
struct point{
    double x,y;
}p[N];

double cross(point a,point b,point c){
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}

double angle(point o,point s,point e)
{
     double cosfi,fi,norm;
     double dsx = s.x - o.x;
     double dsy = s.y - o.y;
     double dex = e.x - o.x;
     double dey = e.y - o.y;
     cosfi=dsx*dex+dsy*dey;
     norm=(dsx*dsx+dsy*dsy)*(dex*dex+dey*dey);
     cosfi /= sqrt( norm );
     if (cosfi >=  1.0 ) return 0;
     if (cosfi <= -1.0 ) return -3.1415926;
     fi=acos(cosfi);
     if (dsx*dey-dsy*dex>0) return fi; 
     return -fi;
}

int main(){
    int n,ans=0;
    point p0;
    p0.x=p0.y=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&p[i].x,&p[i].y);
    }
    for(int i=0;i<n;i++){
        int sum=0,cnt=0;
        for(int j=0;j<n;j++){
            if(i==j) continue;
            if(cross(p[i],p[j],p0)<0) ang[cnt++]=angle(p[j],p[i],p0);
        }
        sort(ang,ang+cnt);
        double ANG=eps;
        for(int i=0;i<cnt;i++){
            if(fabs(ang[i]-ANG)<eps) sum++;
            else{
                ANG=ang[i];
                sum=1;
            }
            ans=max(ans,sum);
        }
    }
    printf("%d",ans+1);
    return 0;
}