题目大意: 在一个雷达的半径范围内扫描一个半圆,求最多能扫到多少个点。
题解: 1.把不在范围内的点排除。 以雷达为圆心构成一个圆。 2.以范围内的点为一条直线平分这个圆,并这2边半圆有分别有多少个点,找最大。 3.一直做第2步,最后输出找到的覆盖最多点的半圆。 判断是否在范围内,用勾股定理。 判断点的位置用计算叉积公式: m=(x1-x0)(y2-y0)-(x2-x0)(y1-y0)
var a:array[0..301,1..2] of real; s,t,w,max,x,y,n,m,i,j,k:longint; px,py,pr:real; begin readln(px,py,pr); while not(eoln) do begin m:=0; max:=0; readln(n); for i:=1 to n do begin readln(x,y); if sqrt(sqr(px-x)+sqr(py-y))<=pr then begin inc(m); a[m,1]:=x; a[m,2]:=y; end; end; for i:=1 to m do begin s:=0; t:=0; w:=0; for j:=1 to m do begin if (a[j,2]-py)*(a[i,1]-px)-(a[j,1]-px)*(a[i,2]-py)=0 then inc(s); if (a[j,2]-py)*(a[i,1]-px)-(a[j,1]-px)*(a[i,2]-py)<0 then inc(t); if (a[j,2]-py)*(a[i,1]-px)-(a[j,1]-px)*(a[i,2]-py)>0 then inc(w); end; if max<t+s then max:=t+s; if max<w+s then max:=w+s; end; writeln(max); readln(px,py,pr); end; end.