雷达覆盖(normal)
Time Limit:1000MS Memory Limit:65536K Total Submit:75 Accepted:35
Description
以雷达心为圆心的半圆形雷达覆盖范围有多个点 雷达可旋转，求最多覆盖数（含在边界的）
分析：先把不能覆盖的点排除，然后用叉积判断覆盖几个点。
计算叉积m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)
代码
const maxn=3000; var x,y:array[0..maxn] of real; max,p,q,s,sum:longint; r,m,xi,yi:real; procedure init; var i,j:longint; begin readln(j); for i:=1 to j do begin readln(p,q); if sqrt(sqr(p-xi)+sqr(q-yi))<=r then begin inc(sum); x[sum]:=p; y[sum]:=q; end; end; end; procedure main; var i,j:longint; begin for i:=1 to sum do begin p:=0;q:=0;s:=0; for j:=1 to sum do begin m:=(x[i]-xi)*(y[j]-yi)-(x[j]-xi)*(y[i]-yi); if m=0 then inc(s); if m>0 then inc(p); if m<0 then inc(q); end; if s+p>max then max:=s+p; if s+q>max then max:=s+q; end; end; begin readln(xi,yi,r); while not (eof(input)) do begin max:=0; sum:=0; init; main; writeln(max); readln(xi,yi,r); end; end.
