题目题解 公式 代码

题目

以雷达心为圆心的半圆形雷达覆盖范围有多个点 雷达可旋转，求最多覆盖数（含在边界的）

题解

由于有多组数据，可以用while not eoln do来循环

可以在读入判断点否在雷达可以覆盖的范围内，即将点到雷达的距离与半径比较，若无法覆盖则不储存该点；（如下图中的点5即无法覆盖）

然后一个循环，依次判断以每个点与雷达所连直线为边界的雷达，然后判断每个点能不能被这样的雷达覆盖。每次都把最多覆盖数与答案比较

! 如图，点O为雷达，若以点2连的线为边界，则点2,1,3以及其他所有在雷达半圆形覆盖范围内的点均可被覆盖。

公式

两点距离公式=sqrt（（x1-x2）(x1-x2)+(y1-y2)(y1-y2))

叉积公式 1.已知：平面上的两点的直角坐标分别为p1(x1,y1)，p2(x2,y2)则 1）该两点相对坐标原点(0,0)的叉积为m=x1*y2-x2*y1 若m>0 则相对坐标原点,点p1在点p2的顺时针方向 若m<0 则相对坐标原点,点p1在点p2的逆时针方向 若m=0 则原点和p1、p2在一条直线上 （2）该两点相对点p0(x0,y0)的叉积为m=(x1-x0)(y2-y0)-(x2-x0)(y1-y0) 若m>0 则相对p0点,点p1在点p2的顺时针方向 若m<0 则相对p0点,点p1在点p2的逆时针方向 若m=0 则p0和p1、p2在一条直线上 2.确定两条连续的有向线段p0p1和p0p2在pl点是向左转还是向右转

(1)计算叉积m=(x1-x0)(y2-y0)-(x2-x0)(y1-y0) （2）判断m 若m>0 则p1点向左拐 若m<0 则p1点向右拐 若m=0 则点p0、p1、p2在一条直线上

例： 350 200 2.0 5 350 202 350 199 350 198 348 200 352 200

代码

var x,y,i,j,l,g,h,ans,n,m:longint; a:array[1..300,1..2]of real; rx,ry,r,c:real; begin readln(rx,ry,r); while not eoln do begin readln(n); l:=0; for i:=1 to n do begin readln(x,y); if sqrt(sqr(rx-x)+sqr(ry-y))<=r then begin inc(l); a[l,1]:=x;a[l,2]:=y; end; end; ans:=0; for i:=1 to l do begin g:=0;h:=0;m:=0; for j:=1 to l do begin c:=(a[j,1]-rx)*(a[i,2]-ry)-(a[j,2]-ry)*(a[i,1]-rx); if (a[j,1]-rx)*(a[i,2]-ry)-(a[j,2]-ry)*(a[i,1]-rx)>0 then inc(g) else if (a[j,1]-rx)*(a[i,2]-ry)-(a[j,2]-ry)*(a[i,1]-rx)<0 then inc(h) else if (a[j,1]-rx)*(a[i,2]-ry)-(a[j,2]-ry)*(a[i,1]-rx)=0 then inc(m); end; if g+m>ans then ans:=g+m; if h+m>ans then ans:=h+m; end; writeln(ans); readln(rx,ry,r); end; end.