Boundary（2020牛客多校）[二]

题目描述

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< n < 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

说明

题目大意

给定坐标系中n个点的坐标，求最多有多少点在同一圆上，且原点也在圆上。

分析

枚举点，然后再枚举另一点，通过圆心公式代出圆心坐标，然后求最多对于同一点一，有多少点二使得圆心同一点，答案+1即可。
（因为有n条线算上原来）

圆心公式

xx=((y[j]-y[i])*y[i]*y[j]-x[i]*x[i]*y[j]+x[j]*x[j]*y[i])/(x[j]*y[i]-x[i]*y[j])
yy=((x[j]-x[i])*x[i]*x[j]-y[i]*y[i]*x[j]+y[j]*y[j]*x[i])/(y[j]*x[i]-y[i]*x[j])

代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define inf 1<<30
using namespace std;
const int MAXN=2010;
ld x[MAXN],y[MAXN];
map<pair<ld,ld>,int> mp;//用map统计
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    	cin>>x[i]>>y[i];
    ll ans=0,now;
    for(int i=1;i<=n;i++){
    	mp.clear();//每次枚举完点一后要清空
    	for(int j=i+1;i<=n;i++){
    		if(x[i]*y[j]-x[j]*y[i]==0) continue;//三点共线无圆
    		ld xx=((y[j]-y[i])*y[i]*y[j]-x[i]*x[i]*y[j]+x[j]*x[j]*y[i])/(x[j]*y[i]-x[i]*y[j]);
			ld yy=((x[j]-x[i])*x[i]*x[j]-y[i]*y[i]*x[j]+y[j]*y[j]*x[i])/(y[j]*x[i]-y[i]*x[j]);
    		++mp[pair<ld,ld>(xx,yy)];
    		ans=max(ans,(ll)mp[pair<ld,ld>(xx,yy)]);
		}
	}
	printf("%lld\n",ans+1);//+1即可
}

END