zju1041 雷达覆盖

    xiaoxiao2021-03-25  104

    雷达覆盖(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.

    转载请注明原文地址: https://ju.6miu.com/read-14502.html

    最新回复(0)