当前位置:网站首页>Jisuanke - t2063_ Missile interception
Jisuanke - t2063_ Missile interception
2022-07-06 01:55:00 【This question AC sleep again】
//
Answer key :
take The distance from the missile to the two systems (d1 d2) Form a structure For missiles to 1 The distance of system No (d1) Sort from big to small
And then we're going to iterate If and only if a[i].d1 + ( 1~i-1 in a[i].d2 The maximum of ) At the very least That's the answer.
Be careful There is such a situation 1 The No. 1 system does not have to intercept any missiles
It is equivalent to dividing the missiles into two piles Ask the sum of their respective maximum values Just arrange the maximum value of one pile first
//
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
typedef struct missile
{
int d1,d2;
}T;
T a[MAXN];
bool cmp( T a,T b )
{
return a.d1>b.d1; // Value of expression
}
int main()
{
int x1,yl,x2,y2,n,i,x,y,maxd2,ans; // yl
while( ~scanf("%d%d%d%d%d",&x1,&yl,&x2,&y2,&n) )
{
memset( a,0,sizeof( a ) );
for( i=0;i<n;i++ )
{
scanf("%d%d",&x,&y);
a[i].d1=( x1-x )*( x1-x )+( yl-y )*( yl-y ); // Negative is positive
a[i].d2=( x2-x )*( x2-x )+( y2-y )*( y2-y );
}
sort( a,a+n,cmp );
ans=a[0].d1; // initialization
maxd2=a[0].d2;
for( i=1;i<=n;i++ ) // i<=n: 1 The system may not need to intercept missiles
{
ans=min( ans,maxd2+a[i].d1 );
maxd2=max( maxd2,a[i].d2 );
}
printf("%d\n",ans);
}
return 0;
}
//
find:
01 Calculation scale 1<=N<=1e5,abs<=1e3 --> d<=2*1e8 < int
02 cmp direct return Value of expression
03 Global variables y1 name conflict Just use yl yi wait ( There is a header file defined y1 )
04 Negative is positive
05 Initialization should be in place (a[n]=0) 1 The system may not need to intercept missiles
06 Clarify the logical relationship
00 Why did you think wrong at first
There may be front 1 System The working radius is large
Then suddenly there is a distance 2 System Near some very far missiles
Lead to direct 1 System The working radius of includes
00 Fast reading
边栏推荐
- 01. Go language introduction
- Unity learning notes -- 2D one-way platform production method
- 2022年PMP项目管理考试敏捷知识点(8)
- How to improve the level of pinduoduo store? Dianyingtong came to tell you
- 同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
- Leetcode skimming questions_ Invert vowels in a string
- Regular expressions: examples (1)
- genius-storage使用文档,一个浏览器缓存工具
- Ali test Open face test
- UE4 unreal engine, editor basic application, usage skills (IV)
猜你喜欢
Leetcode skimming questions_ Verify palindrome string II
使用npm发布自己开发的工具包笔记
Leetcode3. Implement strstr()
How to improve the level of pinduoduo store? Dianyingtong came to tell you
A picture to understand! Why did the school teach you coding but still not
Docker compose configures MySQL and realizes remote connection
Redis-字符串类型
Folio.ink 免费、快速、易用的图片分享工具
National intangible cultural heritage inheritor HD Wang's shadow digital collection of "Four Beauties" made an amazing debut!
Leetcode3, implémenter strstr ()
随机推荐
【Flask】官方教程(Tutorial)-part1:项目布局、应用程序设置、定义和访问数据库
安装php-zbarcode扩展时报错,不知道有没有哪位大神帮我解决一下呀 php 环境用的7.3
Comments on flowable source code (XXXV) timer activation process definition processor, process instance migration job processor
Computer graduation design PHP enterprise staff training management system
Computer graduation design PHP animation information website
02.Go语言开发环境配置
Computer graduation design PHP college student human resources job recruitment network
Card 4G industrial router charging pile intelligent cabinet private network video monitoring 4G to Ethernet to WiFi wired network speed test software and hardware customization
Regular expressions: examples (1)
GBase 8c数据库升级报错
Blue Bridge Cup embedded_ STM32_ New project file_ Explain in detail
PHP campus movie website system for computer graduation design
Computer graduation design PHP college classroom application management system
Flutter Doctor:Xcode 安装不完整
Unity learning notes -- 2D one-way platform production method
同一个 SqlSession 中执行两条一模一样的SQL语句查询得到的 total 数量不一样
Redis daemon cannot stop the solution
Computer graduation design PHP campus restaurant online ordering system
Redis string type
Redis-字符串类型