D-snow halo solution

D- Snow halo problem solution

label ： Analytic geometry

Topic link

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;
}