Description
给定 \(n\) 个点的坐标、半圆的半径以及坐标。问半圆怎么放能覆盖最多的点,输出最多个数。
Solution
计算几何入门题。
首先显然距离圆心超过半径的点是一定不会被覆盖的,舍去。
再者我们考虑,半圆的放法是有无限多种的,我们要考虑哪些是有用的。我们可以想到,最优的半圆一定刚好卡上一个点,这样就能留充足的空间给别的点。因为 \(n\leq150\),所以可以暴力枚举边界,然后用叉积统计一边的点的个数,这样另一边点的个数就是总点数减去这一边点的个数,取个 \(\max\) 统计一下即可。
Code
#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e5 + 5;
const double eps = 1e-6;
const double Pi = acos(-1.0);
using namespace std;
struct Point{
double x,y;
}a[N],p[N],o;
int n,cnt,ans,Max;
double R;
il int read()
{
int f=0,s=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
return f ? -s : s;
}
Point operator +(Point a,Point b) { return Point{a.x+b.x,a.y+b.y}; }//加
Point operator -(Point a,Point b) { return Point{a.x-b.x,a.y-b.y}; }//减
il double operator *(Point a,Point b) { return a.x*b.y - a.y*b.x; }//叉积
il double operator &(Point a,Point b) { return a.x*b.x + a.y*b.y; }//点积
il double cross(Point a,Point b,Point c) { return (b-a)*(c-a); }//判断c和直线ab的关系
il double len(Point a) { return sqrt(a&a); }
il double dis(Point a,Point b) { return len(b-a); }
il void Main()
{
scanf("%lf%lf%lf",&o.x,&o.y,&R);
if(R < 0) exit(0);
n = read();
cnt = Max = ans = 0;
for(re int i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].x,&a[i].y);
if(dis(a[i],o) <= R) p[++cnt] = a[i];//保留有用的
}
n = cnt;
for(re int i=1;i<=n;i++)//枚举边界
{
ans = 0;
for(re int j=1;j<=n;j++)
if(cross(o,p[i],p[j]) <= 0) ans++;//统计一边
Max = max(Max,max(ans,n-ans));
}
cout << Max << "\n";
}
signed main()
{
while(1) Main();
return 0;
}
复杂度 \(O(Tn^2)\),可以通过本题。
标签:ch,Transmitters,int,题解,SP898,long,double,半圆,define From: https://www.cnblogs.com/bloodstalk/p/17433106.html