02.
x,y:integer;
03.
z:longint;
04.
end;
05.
06.var x1,y1,x2,y2,a,b,i,j, k,t,m,n,ans:longint;
07.
ss:array[1..100010]of sss;
08.procedure change(var a,b:sss);
09.
var t:sss;
10.
begin
11.
t:=a;
12.
a:=b;
13.
b:=t;
14.
end;
15.
16.procedure qsort(first,last:longint);
17.
var left,right,mid,k:longint;
18.
begin
19.
k:=(first+last)div 2;
20.
mid:=ss[k].z;
21.
repeat
22.
left:=first;
23.
right:=last;
24.
while ss[left].z>mid do inc(left);
25.
while ss[right].z<mid do dec(right);
26.
if left<right then begin
27.
change(ss[left],ss[right]);
28.
end;
29.
until (right=k)or(left=k);
30.
if first<right-1 then qsort(first,right-1);
31.
if last>left+1 then qsort(left+1,last);
32.
end;
33.
34.begin
35.readln(x1,y1,x2,y2);
36.readln(n);
37.for i:=1 to n do
38.
begin
39.
readln(ss[i].x,ss[i].y);
40.
ss[i].z:=sqr(ss[i].x-x1)+sqr(ss[i].y-y1);
41.
if ss[i].z>ans then ans:=ss[i].z;
42.
end;
43.qsort(1,n);
44.ans:=ss[1].z;
45.for i:=2 to n do
begin
a:=sqr(ss[i-1].x-x2)+sqr(ss[i-1].y-y2);
if b<a then b:=a;
if ans>ss[i].z+b then ans:=ss[i].z+b;
end;
writeln(ans);
end.
一个拦截装置覆盖所有目标,缩小该圆,用另一个装置去覆盖露出来的导弹,若方案更优则更新数据
思路很简单,但只有40分
procedure qsort(head,tail:longint);
var
i,j:longint;
x:sss;
begin
i:=head;
j:=tail;
x:=ss[i];
while i<j do
begin
while(i<j)and(x.z>=ss[j].z) do j:=j-1;
ss[i]:=ss[j];
while(i<j)and(x.z<=ss[i].z) do i:=i+1;
ss[j]:=ss[i];
end;
ss[i]:=x;
if head<i-1 then qsort(head,i-1);
if i+1<tail then qsort(i+1,tail);
end;
这就A了,WHY?