当前位置:网站首页>D-snow halo solution
D-snow halo solution
2022-07-05 15:25:00 【wch(】
D- Snow halo problem solution
label : Analytic geometry
subject
Ideas
The topic is actually relatively simple , Using high school mathematics can do , Unfortunately, I didn't finish reading the title during the competition
But because of IQ offline just now wa It took several rounds to pass
The problem is the shortest distance from a point to a line segment , It needs to be discussed on a case by case basis
First, determine the triangle formed by line segments and points Whether there is obtuse angle on one side of the line segment , You can use vectors to judge .
If a line segment is an edge, there is no obtuse angle Obviously, the shortest distance is the distance between the point and the straight line ,
Available formulas Calculation
If there is obtuse angle Then the shortest distance is the smaller one from the point to both ends of the line
In addition, pay attention not to use long long Otherwise, it will be out of range .
Code implementation
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
int main() {
double ans = 999999999;
double x1, y1, x2, y2;
int n;
cin >> n;
cin >> x1 >> y1;
cin >> x2 >> y2;
x1 -= x2;
y1 -= y2;// Make Xiaoguo at the origin relative to Xiaohong running , Convenient formula calculation
while (n--) {
cin >> x2 >> y2;
x2 += x1;
y2 += y1;
double a, c, d1, d2;
d2 = sqrt(min(x1 * x1 + y1 * y1, x2 * x2 + y2 * y2));
if ((x1 * (x2 - x1) + y1 * (y2 - y1) >= 0)||(x2*(x1-x2)+y2*(y1-y2)>=0)) ans = min(ans, d2);
else {
if (x1 - x2 != 0) {
a = (y1 - y2) / (x1 - x2);
c = y1 - a * x1;// A straight line -ax+y-c=0;
d1 = abs(c) / sqrt(a * a + 1);
ans = min(ans, d1);
}
else ans = min(ans, abs(x1));
}
x1 = x2;
y1 = y2;
}
printf("%0.12lf", ans);
return 0;
}
边栏推荐
- I want to inquire about how to ensure data consistency when a MySQL transaction updates multiple tables?
- Bugku easy_ nbt
- Brief introduction of machine learning framework
- 计算中间件 Apache Linkis参数解读
- Mysql---- function
- 想问下大家伙,有无是从腾讯云MYSQL同步到其他地方的呀?腾讯云MySQL存到COS上的binlog
- qt creater断点调试程序详解
- GPS原始坐标转百度地图坐标(纯C代码)
- ionic cordova项目修改插件
- How to paste the contents copied by the computer into mobaxterm? How to copy and paste
猜你喜欢
Bugku's eyes are not real
Object. defineProperty() - VS - new Proxy()
Your childhood happiness was contracted by it
Thymeleaf uses background custom tool classes to process text
超越PaLM!北大碩士提出DiVeRSe,全面刷新NLP推理排行榜
30岁汇源,要换新主人了
Ionic Cordova project modification plug-in
Ctfshow web entry command execution
P6183 [USACO10MAR] The Rock Game S
Visual task scheduling & drag and drop | scalph data integration based on Apache seatunnel
随机推荐
Dark horse programmer - software testing -10 stage 2-linux and database -44-57 why learn database, description of database classification relational database, description of Navicat operation data, de
NBA赛事直播超清画质背后:阿里云视频云「窄带高清2.0」技术深度解读
wxml2canvas
GPS原始坐标转百度地图坐标(纯C代码)
mapper.xml文件中的注释
queryRunner. Query method
Bugku's eyes are not real
mapper. Comments in XML files
Crud of MySQL
Thymeleaf uses background custom tool classes to process text
Coding devsecops helps financial enterprises run out of digital acceleration
Interpretation of Apache linkage parameters in computing middleware
Garbage collection mechanism of PHP (theoretical questions of PHP interview)
Array sorting num ranking merge in ascending order
SQL Server learning notes
I collect multiple Oracle tables at the same time. After collecting for a while, I will report that Oracle's OGA memory is exceeded. Have you encountered it?
ICML 2022 | explore the best architecture and training method of language model
Bubble sort, insert sort
How to paste the contents copied by the computer into mobaxterm? How to copy and paste
Ctfshow web entry information collection