题目描述
以雷达心为圆心的半圆形雷达覆盖范围有多个点 雷达可旋转，求最多覆盖数（含在边界的）
样例输入
25 25 3.5－－－－－－雷达坐标与半径 7－－－－－－－－－－点数 25 28－－－－－－－点坐标 23 27 27 27 24 23 26 23 24 29 26 29 350 200 2.0 5 350 202 350 199 350 198 348 200 352 200 995 995 10.0 4 1000 1000 999 998 990 992 1000 999 100 100 -2.5
样例输出
3 4 4
思路
O(km^2)
先把雷达范围内的点用勾股定理剔除，再以每个点和圆心的直线为直径，计算左边和右边的点数，覆盖的点数要加上在直径上的点。
var
x,y:
array[
1..1000] of longint;
n,a,b,c:double;
m,i,j,k,l,r,
mid,max:longint;
begin
readln(a,b,n);
while not eof(input)
do
begin
readln(m);j:=
0;
for i:=
1 to m
do
begin
inc(j);
readln(x[j],y[j]);
if sqrt(
sqr(a-x[j])+
sqr(b-y[j]))>n
then
dec(j);
end;
max:=
0;
for i:=
1 to j
do
begin
mid:=
0;l:=
0;r:=
0;
for k:=
1 to j
do
begin
c:=(y[k]-b)*(x[i]-a)-(x[k]-a)*(y[i]-b);
if c=
0 then inc(
mid);
if c<
0 then inc(l);
if c>
0 then inc(r);
end;
if l+
mid>max
then max:=l+
mid;
if r+
mid>max
then max:=r+
mid;
end;
writeln(max);
readln(a,b,n);
end;
end.
转载请注明原文地址: https://ju.6miu.com/read-24125.html
