题解 P1158 【导弹拦截】

Komes · 2017-08-25 20:14:36 · 题解

这道题其实不难，最主要的是看清楚题目。这道题我第一眼看，我就肯定是用贪心。。但是我一开始没考虑到这个还要排序，结果就WA了，，然后我还傻傻的去找我的程序有啥子错误，结果，一直都找不到然后我突然灵光一闪，这个要不要排序呢，然后想着想着感觉好像真的要排序。然后就速度添加了一个快排，然后就过了。所以说，找到算法是一回事，最后要看你如何实现这个算法。

Var
        x1,y1,x2,y2,i,jl,jl1,num,n:longint;
        b,c,a:array[1..100000]of longint;
Procedure quicksort(l,r:longint);         //快排
Var
        i,j,mid,t:longint;
Begin
        i:=l; j:=r; mid:=a[(i+j) div 2];
        repeat
                while a[i]>mid do inc(i);
                while a[j]<mid do dec(j);
                if i<=j then
                begin
                        t:=a[i]; a[i]:=a[j]; a[j]:=t;
                        t:=b[i]; b[i]:=b[j]; b[j]:=t;
                        t:=c[i]; c[i]:=c[j]; c[j]:=t;   //这里要把坐标一起变更。
                        inc(i); dec(j);
                end;
        until i>j;
        if i<r then quicksort(i,r);
        if l<j then quicksort(l,j);
End;
Begin
        readln(x1,y1,x2,y2);
        readln(n);
        for i:=1 to n do
        begin
                readln(b[i],c[i]);  //这个要储存坐标；
                a[i]:=sqr(b[i]-x1)+sqr(c[i]-y1);  //计算代价
        end;
        quicksort(1,n);
        num:=a[1];    //初值要赋a【1】（你不想a【1】也可以，但不能是maxlongint，因为下面的枚举是1 to n-1）
        for i:=1 to n-1 do
        begin
                jl:=sqr(b[i]-x2)+sqr(c[i]-y2); //计算第二套系统拦截的代价。
                if jl>jl1 then  //看下当前代价是否大于之前的代价，是就把最大的代价变更为当前的代价。
                        jl1:=jl;
                if jl1+a[i+1]<num then  
                        num:=jl1+a[i+1];
        end;
        writeln(num);
        readln;
End.