提供网站建设运营公司资质,呼和浩特百度seo,wordpress插件放那个文件夹,哪个兄弟来个直接看的网站题意#xff1a;给定一个点#xff0c;一个圆#xff0c;以及一个矩形#xff0c;现在问从一个点到一个圆再到一个矩形的最短距离为多少#xff1f;到达一个目标可以只挨着或者穿过它。 解法#xff1a;目前只知道从一个点到圆上按照[0,PI]#xff0c;[PI,2*PI]的两个半…题意给定一个点一个圆以及一个矩形现在问从一个点到一个圆再到一个矩形的最短距离为多少到达一个目标可以只挨着或者穿过它。 解法目前只知道从一个点到圆上按照[0,PI][PI,2*PI]的两个半圆进行划分确实是满足距离是一个凹函数但是加上到矩形的距离后仍然满足三分性质则不知道怎么得到的。具体做法是先将整个坐标系平移使得圆心落在(0, 0)处然后三分枚举圆上的点距离由两部分组成一部分是点到圆上点的距离一部分是点到矩形的距离后者转化为点到四条线段的距离求解。 代码如下 #include cstdlib
#include cstring
#include cstdio
#include algorithm
#include iostream
#include cmath
using namespace std;const double eps 1e-6;
const double PI acos(-1.0);
double cx, cy, cr; // 圆的圆心以及半径inline int sign(double x) {return x -eps ? -1 : x eps ? 1 : 0;
}struct Point {double x, y;Point (double xx 0, double yy 0) : x(xx), y(yy) {}Point operator - (const Point ot) const { // 两个点作差获得向量 return Point(x - ot.x , y - ot.y);}double operator * (const Point ot) const { // 重载点积return x * ot.x y * ot.y;}double operator ^ (const Point ot) const { // 重载叉积 return x * ot.y - y * ot.x;}bool operator (const Point ot) const {if (sign(x - ot.x)) {return sign(x - ot.x) 0; // 首先按照横坐标排序 } else { // 然后按照纵坐标排序 return sign(y - ot.y) 0;}}void show() {printf(x %.2f, y %.2f\n, x, y);}
};Point it, rp[4];double dist(const Point a, const Point b) {return sqrt((a.x-b.x)*(a.x-b.x) (a.y-b.y)*(a.y-b.y));
}double dtoL(const Point np, const Point st, const Point ed) { // 点到线段的距离 double ret; if (sign((ed-st)*(np-st)) 0 sign((st-ed)*(np-ed) 0)) { // 用来判定一个该点的投影在该线段上ret fabs((st-np)^(ed-np)) / dist(st, ed);} else {ret min(dist(np, st), dist(np, ed)); // 点到两个端点的较小值}return ret;
}double dtoR(const Point np) { // 到四条线段的最短距离 double d1 min(dtoL(np, rp[0], rp[1]), dtoL(np, rp[0], rp[2]));double d2 min(dtoL(np, rp[1], rp[3]), dtoL(np, rp[2], rp[3]));return min(d1, d2);
}double tsearch(double l, double r) {double delta;while (r - l eps) {delta (r - l) / 3.0; // delta表示是区间长度的1/3Point Lp(cr*cos(ldelta), cr*sin(ldelta));Point Rp(cr*cos(r-delta), cr*sin(r-delta));double d1 dist(it, Lp) dtoR(Lp);double d2 dist(it, Rp) dtoR(Rp);if (sign(d1 - d2) 0) {l delta;} else {r - delta;}}Point fp(cr*cos(r), cr*sin(r));return dist(it, fp) dtoR(fp);
}void solve() {// 先三分[0, PI]在三分[PI, 2*PI]内的角度printf(%.2f\n, min(tsearch(0, PI), tsearch(PI, 2*PI)));
}int main() {while (scanf(%lf %lf, it.x, it.y), sign(it.x) | sign(it.y)) {scanf(%lf %lf %lf, cx, cy, cr); // 读取圆心坐标和半径it.x - cx, it.y - cy; // 将圆心平移到源点其余坐标均作出改变scanf(%lf %lf, rp[0].x, rp[0].y);rp[0].x - cx, rp[0].y - cy;scanf(%lf %lf, rp[1].x, rp[1].y);rp[1].x - cx, rp[1].y - cy;rp[2].x rp[0].x, rp[2].y rp[1].y;rp[3].x rp[1].x, rp[3].y rp[0].y;sort(rp, rp4); // 获得矩形的四个顶点并排序方便得到线段与点的关系double t sqrt(2.0) / 2;solve();}return 0;
} 转载于:https://www.cnblogs.com/Lyush/archive/2013/05/30/3108485.html
