题目描述
经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。
某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦截所有的导弹，请计算这一天的最小使用代价。

【提示】
两个点(x1, y1)、(x2, y2)之间距离的平方是(x1−；；； x2)^2+(y1−；；；y2)^2。
两套系统工作半径r1、r2 的平方和，是指r1、r2 分别取平方后再求和，即r1^2+r2^2。

【样例 1 说明】
样例1 中要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分
别为18 和0。
【样例2 说明】
样例中的导弹拦截系统和导弹所在的位置如下图所示。要拦截所有导弹，在满足最小使用代价的前提下，两套系统工作半径的平方分别为20 和10。



【数据范围】
对于10%的数据，N = 1
对于20%的数据，1 ≤ N ≤ 2
对于40%的数据，1 ≤ N ≤ 100
对于70%的数据，1 ≤ N ≤ 1000
对于100%的数据，1 ≤ N ≤ 100000，且所有坐标分量的绝对值都不超过1000。

输入格式
第一行包含4 个整数x1、y1、x2、y2，每两个整数之间用一个空格隔开，表示这两套导
弹拦截系统的坐标分别为(x1, y1)、(x2, y2)。
第二行包含1 个整数N，表示有N 颗导弹。接下来N 行，每行两个整数x、y，中间用
一个空格隔开，表示一颗导弹的坐标(x, y)。不同导弹的坐标可能相同。

输出格式
输出只有一行，包含一个整数，即当天的最小使用代价。

样例输入
【输入输出样例1】
0 0 10 0
2
-3 3
10 0

【输入输出样例2】
0 0 6 0
5
-4 -2
-2 3
4 0
6 -2
9 1
样例输出
【输入输出样例1】
18

【输入输出样例2】
30

不知各位高手对这题有什么见解？

[ 本帖最后由 sunyh1999 于 2010-11-28 20:14 编辑 ]

无语了，没想到放到评测系统上一测，竟然AC了，还是最优解~~~~~~~~~~~

原来测试数据中有一个数据是很奇怪的符号，所以拖在那里.....

现在改一下题目~~

你这个样例过了吗？  还有10W个数据用冒泡，好像慢了点

为什么要动态分配呢？你可以定义一个数组，然后用qsort函数，就能快速排序：
qsort(array,n,sizeof(array[0]),comp);

找到了一个pascal AC的程序。

program rq604missile;
 type
     ret=record
         x,y,dis:longint;
         end;
 var
    x1,y1,x2,y2,n,i,ans,r:longint;
    a:array[1..100000]of ret;

 procedure qsort(head,tail:longint);
  var
     i,j:longint;
     x:ret;
  begin
       i:=head;j:=tail;x:=a[i];
       while i<j do
        begin
             while(i<j)and(x.dis>=a[j].dis) do j:=j-1;
             a[i]:=a[j];
             while(i<j)and(x.dis<=a[i].dis) do i:=i+1;
             a[j]:=a[i];
        end;
       a[i]:=x;
       if head<i-1 then qsort(head,i-1);
       if i+1<tail then qsort(i+1,tail);
  end;

 function dist(a,b,c,d:longint):longint;
  begin
       dist:=sqr(a-c)+sqr(b-d);
  end;

 procedure init;
  begin
       readln(x1,y1,x2,y2);
       readln(n);
       for i:=1 to n do
        begin
             with a[i] do
              begin
                   readln(x,y);
                   dis:=dist(x,y,x1,y1);
              end;
        end;
       qsort(1,n);
       r:=0;
  end;

 procedure work;
  begin
       ans:=a[1].dis;
       for i:=2 to n do
        begin
             with a[i-1] do
              begin
                   if r<dist(x2,y2,x,y) then r:=dist(x2,y2,x,y);
                   if ans>a[i].dis+r then ans:=a[i].dis+r;
              end;
        end;
  end;

 begin
      init;
      work;
      writeln(ans);
      close(input);
 end.

麻烦帮我写一下代码，让我看看，我坐标还没有学呢。。
听说这题先用快排，然后贪心，就可以了