B Boundary（计算几何） 2020牛客暑期多校训练营（第二场）

本文主要是介绍B Boundary（计算几何） 2020牛客暑期多校训练营（第二场），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

题意：
求一个圆（保证经过原点），覆盖（点在圆周上）最多的点。求点数

思路：
3点求圆心，最后排序来算多少个圆心一样（因为一定经过原点，所以不需要确定半径）。但感觉还是数据水了，这样写还用了double很容易被卡精度。

正解的意思是同弧所对圆心角相等，所以你固定一个点，再枚举其他点看多少个角度相等取最大值。

但是这个过程不能出现下面的情况。只需要规定A只能出现在OP下方即可，也就是OP与OA叉积为负。

在这里插入图片描述

#pragma GCC optimize(2)#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <ctime>
#include <cstdlib>using namespace std;
const int maxn = 1e5 + 7;bool same(double x,double y) {if(fabs(x - y) < 1e-9) return true;return false;
}struct Point {double x,y;bool operator < (const Point&rhs) const {if(same(x,rhs.x)) return y < rhs.y;return x < rhs.x;}bool operator == (const Point&rhs) const {return same(x,rhs.x) && same(y,rhs.y);}
}a[maxn],O; //O为圆心int n;
double R; //半径double dis(Point a,Point b) {return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}bool check(Point p1,Point p2,Point p3) { //3点求圆心if((p1.x - p2.x) * (p1.y - p3.y) == (p1.x - p3.x) * (p1.y - p2.y)) {return false;}double a1 = ((p1.x * p1.x - p2.x * p2.x) + (p1.y * p1.y - p2.y * p2.y)) / 2;double a2 = ((p1.x * p1.x - p3.x * p3.x) + (p1.y * p1.y - p3.y * p3.y)) / 2;O.x = ((p1.y - p2.y) * a2 - (p1.y - p3.y) * a1) / ((p1.y - p2.y) * (p1.x - p3.y) - (p1.x - p2.x) * (p1.y - p3.y));O.y = ((p1.x - p3.x) * a1 - (p1.x - p2.x) * a2) / ((p1.y - p2.y) * (p1.x - p3.x) - (p1.x - p2.x) * (p1.y - p3.y));return true;
}vector<Point>vec;int main() {scanf("%d",&n);for(int i = 1;i <= n;i++) {scanf("%lf%lf",&a[i].x,&a[i].y);}a[0].x = a[0].y = 0;for(int i = 1;i <= n;i++) {for(int j = i + 1;j <= n;j++) {if(!check(a[i],a[j],a[0])) continue;vec.push_back(O);}}sort(vec.begin(),vec.end());int ans = 1;for(int i = 0;i < vec.size();) {int j = i;while(j < vec.size() && vec[i] == vec[j]) {j++;}int num = j - i;ans = max(ans,(int)floor((-1 + sqrt(1 + 8 * num)) / 2.0) + 1);i = j;}printf("%d\n",ans);return 0;
}