本文主要是介绍poj 1981 单位圆套最多点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给n（300）个点，用单位圆去套他们，问最多能套多少个点。
解析：
点击打开链接
直接当作单位圆套最多点的模板吧，用极脚来排序。
代码：
#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 300 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;struct Point
{double x, y;Point(){}Point(double _x, double _y){x = _x;y = _y;}
} point[maxn];struct polarAngle
{double angle;bool tag; //起点or终点const bool operator<(const polarAngle &other)const{if (angle == other.angle)return tag > other.tag;return angle < other.angle;}
} polarangle[maxn];double dist(Point a, Point b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}int maxCircleCover(int n, double r)
{int res = 1;for (int i = 0; i < n; i++){int tot = 0;double d;for (int j = 0; j < n; j++){if (i != j && (d = dist(point[i], point[j])) <= 2){double phi = acos(d / 2);double theta = atan2(point[j].y - point[i].y, point[j].x - point[i].x);polarangle[tot].angle = theta - phi;polarangle[tot++].tag = true;polarangle[tot].angle = theta + phi;polarangle[tot++].tag = false;}}sort(polarangle, polarangle + tot);int sum = 1;for (int j = 0; j < tot; j++){if (polarangle[j].tag)sum++;elsesum--;res = Max(res, sum);}}return res;
}Point readPoint()
{double x, y;scanf("%lf %lf", &x, &y);return Point(x, y);
}int main()
{
#ifdef LOCALFIN;
#endif // LOCALint n;while (~scanf("%d", &n) && n){for (int i = 0; i < n; i++){point[i] = readPoint();}printf("%d\n", maxCircleCover(n, 1.0));}return 0;
}
这篇关于poj 1981 单位圆套最多点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
