当前位置:首页 >> 学科竞赛 >> 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 解题报告(提高) 作者:张宇昊所有见解仅供参考 考试时。。。发挥 1/3 已经不错了。。真理。。! 考试结束。。觉得题都可做。。。 No1. 1.机器翻译 ...

NOIP2010普及组复赛试题

NOIP2010普及组复赛试题_初三数学_数学_初中教育_教育专区。NOIP2010普及组复赛...导弹拦截 missile 三国游戏 sanguo two water missile sanguo two.in water.in ...

NOIP2010普及组满分题解

NOIP2010普及组满分题解_IT/计算机_专业资料。【个人题解+代码】NOIP2010 普及...end 3.导弹拦截 (missile.pas/c/cpp) 【问题描述】 经过 11 年的韬光养晦...

NOIP2010普及组解题报告(C++)由锦云收集

NOIP2010普及组解题报告(C++)由锦云收集_IT/计算机_专业资料。如题2010...三、导弹拦截 再次见到导弹拦截, 颇感亲切, 但是这次的导弹拦截, 加入了立体...

NOIP2010普及组解题报告

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

NOIP2010普及组个人解题报告

NOIP2010普及组个人解题报告_IT/计算机_专业资料。1.数字统计 . (two.pas/c/...3.导弹拦截 . (missile.pas/c/cpp) 【问题描述】 经过 11 年的韬光养晦,...

NOIP2010普及组复赛试题

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

2010NOIP必备代码

(s,fout);输出字串 5,Catalan 数 By Victor Zhang for 2010NOIP 是操作数则进 num 栈,若是运算符则 和 opt 栈的栈顶元素比较优先级,规 则如下 a.如果...

noip2010普及组复赛解题报告

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

2010NOIP模拟测试与题解

7页 免费 NOIP2010集训小资料 13页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
更多相关标签:
noip2010导弹拦截 | 导弹拦截 noip | noip1999导弹拦截 | 洲际导弹无法拦截 | 弹道导弹为什么难拦截 | 洲际导弹可以拦截吗 | 导弹拦截 | 中国导弹拦截系统 |
网站地图

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