当前位置:网站首页>Missile interception -- UPC winter vacation training match
Missile interception -- UPC winter vacation training match
2022-07-05 01:50:00 【Porter hunter of the program】
subject
Background
after 11 Years of hiding one's strength and cultivating one's obscurity , A country has developed a new missile interception system , Any missile whose distance from it does not exceed its working radius can be successfully intercepted by it . When the working radius is 0 when , It can intercept missiles in exactly the same position . But the missile interception system also has such defects : Each system can only set the working radius once a day . And the use cost of the day , Is the sum of the squares of the working radii of all systems .
One day , The radar caught the enemy's missiles coming . Because the system is still in the experimental stage , So only two systems are working . If the current requirement is to intercept all missiles , Please calculate the minimum use cost of this day .
Input
The first line contains 4 It's an integer x1、y1、x2、y2, Every two integers are separated by a space , The coordinates of the two missile interception systems are (x1,y1)、(x2,y2).
The second line contains 1 It's an integer N(1≤N≤100000), Express N Missiles . Next N That's ok , Two integers per line x、y, Separated by a space , Represents the coordinates of a missile (x,y). The coordinates of different missiles may be the same .
Output
There is only one line of output , Contains an integer , That is, the minimum use cost of the day .
The sample input
0 0 10 0 2 -3 3 10 0
Sample output
18
Tips and data range limitations
Two points (x1,y1)、(x2,y2) The square of the distance between is (x1−x2)2+(y1−y2)2.
The working radius of the two systems r1、r2 Sum of squares of , Refer to r1、r2 Take the squares respectively and then sum , namely r12+r22.
about 100% The data of ,1≤N≤100000, And the absolute value of all coordinate components does not exceed 1000.
Thought analysis
Wrong thinking : At the beginning of this question, I thought that this missile was intercepted by the nearest interception system , But the result is WA.
Ah , Still too simple .If you follow my idea , Later, I came up with a good example , On a number axis ,0 and 5 Is the location of the interception system , Now if it's in -5 and 4 There is a missile at , Obviously, our previous thinking is wrong , This only needs to be used in 0 The interception system of the location is ok .The right way of thinking : The correct way to do this is to follow 1 Sort by the distance of , Then find a suitable dividing point i Make part of it intercepted by the first interception system , The other part is intercepted by the second interception system . In this way, we can find the minimum sum of squares
I don't say much nonsense , Code up
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll xa,xb,ya,yb;
struct node{
ll x,y;
ll disa,disb;
}a[N];
ll da,db;
ll n;
bool cmp(node c,node d){
return c.disa>d.disa;
}
int main()
{
cin>>xa>>ya>>xb>>yb;// Enter the location coordinates of the two interception systems
cin>>n;// Enter the number of missiles
for(ll i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;// Enter the first i Position coordinates of missiles
a[i].disa=(a[i].x-xa)*(a[i].x-xa)+(a[i].y-ya)*(a[i].y-ya);// Calculate to a The square of the distance
a[i].disb=(a[i].x-xb)*(a[i].x-xb)+(a[i].y-yb)*(a[i].y-yb);// Calculate to b The square of the distance
}
sort(a+1,a+1+n,cmp);// Sort according to the position from the first interception system
ll ans=INT_MAX;// Define a variable to store the answer , Assign the initial value to infinity
ll r2=0;// Define a variable to record the radius set by the second interception system
for(ll i=1;i<=n+1;i++){
ll r1=a[i].disa;// Radius of the first interception system
r2=max(r2,a[i-1].disb);// Find the interception radius of the second interception system
ans=min(r1+r2,ans);// Find the most suitable decomposition point is the sum of the squares of the minimum distance
}
cout<<ans;
return 0;
}
Examples of operation process
边栏推荐
- Incremental backup? db full
- MySQL REGEXP:正则表达式查询
- pytorch fine-tuning (funtune) : 镂空设计or 偷梁换柱
- Great God developed the new H5 version of arXiv, saying goodbye to formula typography errors in one step, and mobile phones can also easily read literature
- Redis' hyperloglog as a powerful tool for active user statistics
- 172. Zero after factorial
- 微信小程序:独立后台带分销功能月老办事处交友盲盒
- Phpstrom setting function annotation description
- 流批一體在京東的探索與實踐
- Li Kou Jianzhi offer -- binary tree chapter
猜你喜欢
Application and Optimization Practice of redis in vivo push platform
Three properties that a good homomorphic encryption should satisfy
JS implementation determines whether the point is within the polygon range
DOM basic syntax
. Net starts again happy 20th birthday
力扣剑指offer——二叉树篇
微信小程序:最新wordpress黑金壁纸微信小程序 二开修复版源码下载支持流量主收益
MATLB|多微电网及分布式能源交易
Practice of tdengine in TCL air conditioning energy management platform
Blue Bridge Cup Square filling (DFS backtracking)
随机推荐
Redis' hyperloglog as a powerful tool for active user statistics
Phpstrom setting function annotation description
Change the background color of a pop-up dialog
Yyds dry inventory swagger positioning problem ⽅ formula
如何搭建一支搞垮公司的技術團隊?
Runc hang causes the kubernetes node notready
The steering wheel can be turned for one and a half turns. Is there any difference between it and two turns
Database postragesq PAM authentication
Nebula importer data import practice
Classification of performance tests (learning summary)
Win:使用组策略启用和禁用 USB 驱动器
JS implementation determines whether the point is within the polygon range
Pytorch fine tuning (Fortune): hollowed out design or cheating
The perfect car for successful people: BMW X7! Superior performance, excellent comfort and safety
Application and Optimization Practice of redis in vivo push platform
batchnorm.py这个文件单GPU运行报错解决
MATLB|多微电网及分布式能源交易
PHP 基础篇 - PHP 中 DES 加解密详解
Express routing, express middleware, using express write interface
MATLB | multi micro grid and distributed energy trading