当前位置:首页 >> 学科竞赛 >> NOIP2010 missile导弹拦截

NOIP2010 missile导弹拦截


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

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

输出格式:
输出文件名 missile.out。 输出只有一行,包含一个整数,即当天的最小使用代价。

输入输出样例 1
missile.in 0 0 10 0 2 -3 3 10 0 missile.out 18

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

- 1 –

2010-11-25

NOIP2010 missile 导弹拦截 输入输出样例 2
missile.in 0060 5 -4 -2 -2 3 40 6 -2 91 missile.out 30

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

数据范围:
对于 10%的数据有 n=1;。 对于 20%的数据有 1 ? n ? 2; 对于 40%的数据有 1 ? n ? 100;。 对于 70%的数据有 1 ? n ? 1,000; 对于 100%的数据有 1 ? n ? 100,000。且所有坐标分量的绝对值都不超过 1,000。

- 2 –

2010-11-25

NOIP2010 missile 导弹拦截 算法分析:
var a:array[1..100000,1..2] of longint; x1,x2,y1,y2,x,y,n,i,r2,ans:longint; procedure fs(s,e:longint); var m,k,j:longint; ms:array[1..2] of longint; begin m:=random(e-s+1)+s;k:=s;j:=e; ms:=a[m];a[m]:=a[k]; while k<j do begin while (k<j)and(a[j,1]>ms[1]) do dec(j); if k<j then begin a[k]:=a[j];inc(k);end; while (k<j)and(a[k,1]<ms[1]) do inc(k); if k<j then begin a[j]:=a[k];dec(j);end; end; a[k]:=ms; if s<k-1 then fs(s,k-1); if j+1<e then fs(j+1,e); end; begin assign(input,'missile.in');reset(input); assign(output,'missile.ans');rewrite(output); readln(x1,y1,x2,y2); readln(n); for i:=1 to n do begin read(x,y); a[i,1]:=sqr(x-x1)+sqr(y-y1); a[i,2]:=sqr(x-x2)+sqr(y-y2); end; fs(1,n); ans:=a[n,1]; for i:=n downto 1 do begin if a[i,1]+r2<ans then ans:=a[i,1]+r2; if a[i,2]>r2 then r2:=a[i,2]; end; writeln(ans); close(input);close(output); end.

- 3 –

2010-11-25


更多相关文档:

NOIP2010普及组满分题解

NOIP2010普及组满分题解_IT/计算机_专业资料。【个人题解+代码】NOIP2010 普及...missile.out 30 【样例 2 说明】 样例中的导弹拦截系统和导弹所在的位置如下...

NOIP2010普及组解题报告

NOIP2010普及组解题报告_调查/报告_表格/模板_应用文书...T3 : missile 此题是排序+枚举 首先计算出每个点...导弹” 前面的导弹 就是第一个拦截系统所要拦截的...

noip2010普及组复赛解题报告

第三题两个导弹,求拦截导弹的最小和半径(半径的平方和) 难度:★★★☆ 时间...const inf='missile.in'; ouf='missile.out'; var x1,x2,y1,y2,i,j,...

NOIP2010潍坊市选拔赛_提高组

NOIP2010潍坊市选拔赛 提高组试题NOIP2010潍坊市选拔赛 提高组试题隐藏>> 2010 ...128M 导弹拦截 missile.pas/c/cpp missile.in missile.out 1 秒,128M 工作...

NOIP2010普及组复赛试题

NOIP2010普及组复赛试题_司法考试_资格考试/认证_教育专区。全国信息学奥林匹克联赛...导弹拦截 water missile water missile water.in missile.in water.out missile...

NOIP2010普及组复赛试题

NOIP2010普及组复赛试题_学科竞赛_初中教育_教育专区。这是NOIP题目NOIP...water.in water.out 5 3 4 4 1 2 1 4 3.导弹拦截(missile.pas/c/cpp...

2010普及解题报告

那么理所当然, 这个排在 这个导弹之后的点就是系统二所要拦截的, 于是第二个...NOIP2010 普及组 T3 missile 2 3 a:Array[1..100000,1..2] of longint...

NOIP2010普及组解题报告

NOIP2010普及组解题报告_IT/计算机_专业资料。===文件名:解题报告.pas=== 全国...{ ID: jinyu121 PROG: 导弹拦截 LANG: PASCAL } const filename='missile';...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com