2010年noip复赛第三题导弹拦截答案（Pascal语言）请给我思路和标准程序（标程可以省略,但思路情讲清晰,
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 18:43:08
2010年noip复赛第三题导弹拦截答案（Pascal语言）请给我思路和标准程序（标程可以省略,但思路情讲清晰,
2010年noip复赛第三题导弹拦截答案（Pascal语言）
请给我思路和标准程序（标程可以省略,但思路情讲清晰,
2010年noip复赛第三题导弹拦截答案（Pascal语言）请给我思路和标准程序（标程可以省略,但思路情讲清晰,
本题明显是贪心法.我们可以先确定一号系统的半径的平方,在确定二号系统的半径的平方.首先,用一个dis1数组记录下每一个点到一号系统的距离,num1数组记录对应的序号,从小到大快排.然后依次以dis1[1]、dis1[2].为一号系统半径的平方,由于经过排序,dis1[i]即为一号系统的半径,关键在于找出二号系统的半径,即找出剩下导弹中到二号系统距离最远的那个导弹.若用普通的穷举,则程序复杂度接近O(n²),显然不能接受,于是便想到一种新的思路.我们再用一个dis2数组记录下每一个点到二号系统的距离,num2数组记录对应的序号,从小到大快排.每次找最大距离时,就从大到小扫描,直到找到一个num2[i]没有被一号系统拦截即可暂停,此时的dis2[i]即为最大距离.注意,由于dis2[n],dis2[n-1].是递减的,所以扫描时可以直接从上一次扫描结束的地方继续向下扫描.
以下是程序：
type arr=array[0..100000] of longint;
var dis1,dis2,num1,num2:arr; //分别记录每个导弹的坐标到一、二号拦截系统的距离的平方和对应的序号
x,y:array[1..100000] of longint; //记录每个导弹的坐标
x1,y1,x2,y2,n,min:longint;
procedure init;
var i:longint;
begin
readln(x1,y1,x2,y2);
readln(n);
for i:=1 to n do
begin
readln(x[i],y[i]);
dis1[i]:=sqr(x[i]-x1)+sqr(y[i]-y1); //计算距离的平方
num1[i]:=i;
dis2[i]:=sqr(x[i]-x2)+sqr(y[i]-y2);
num2[i]:=i;
end;
dis1[0]:=0;
dis2[0]:=0;
num1[0]:=0;
num2[0]:=0;
end;
procedure qsort(var dis,num:arr; l,r:longint); //快排
var i,j,x,temp:longint;
begin
i:=l;
j:=r;
x:=dis[(l+r) div 2];
while i