HDU-4454 Stealing a Cake
题意： 给定一个点， 圆和矩形。 求这个点到圆和再从圆到矩形的最短距离之和。
分析： 很明显这个距离是一个凹函数， 我们要求这个极值点， 这里用到三分， 标准解法， 要注意的是， 需要分为两个部分[0, pi]和[pi, 2*pi]。是因为他的函数图像是这样的。
所以我们要分成两个部分分别求极值， 然后取最小值即可。
代码：
#include <bits/stdc++.h>using namespace std;const double pi = acos(-1.0);
const double eps = 1e-8;
const double inf = 0x3f3f3f3f;
int sgn(double x)
{
if (fabs(x) < eps)return 0;else if (x < 0)return -1;elsereturn 1;
}struct Point
{
double x, y;Point() {
}Point(double _x, double _y){
x = _x;y = _y;}Point operator+(const Point b) const{
return Point(x + b.x, y + b.y);}Point operator-(const Point b) const{
return Point(x - b.x, y - b.y);}double operator^(const Point b) const{
return x * b.y - y * b.x;}double operator*(const Point b) const{
return x * b.x + y * b.y;}double distance(Point p){
return hypot(x - p.x, y - p.y);}
};struct Line
{
Point s, e;Line() {
}Line(Point _s, Point _e){
s = _s;e = _e;}double length(){
return s.distance(e);}double dispointtoline(Point p){
return fabs((p - s) ^ (e - s)) / length();}double dispointtoseg(Point p){
if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)return min(p.distance(s), p.distance(e));return dispointtoline(p);}
};
Point st, c1, t1, t2;
double r;Point getPoint(double angle)
{
double xx = c1.x + r * cos(angle);double yy = c1.y + r * sin(angle);return Point(xx, yy);
}
double getdist(Point p)
{
Line l1(t1, Point(t1.x, t2.y));Line l2(t1, Point(t2.x, t1.y));Line l3(t2, Point(t1.x, t2.y));Line l4(t2, Point(t2.x, t1.y));double res = inf;res = min(res, l1.dispointtoseg(p));res = min(res, l2.dispointtoseg(p));res = min(res, l3.dispointtoseg(p));res = min(res, l4.dispointtoseg(p));return res;
}
double solve()
{
double l, r, mid, midmid;double ans = inf;Point p1, p2;double dis1, dis2;l = 0, r = pi;while (r - l >= eps){
mid = (l + r) / 2;midmid = (mid + r) / 2;p1 = getPoint(mid);p2 = getPoint(midmid);dis1 = p1.distance(st) + getdist(p1);dis2 = p2.distance(st) + getdist(p2);if (dis1 > dis2)l = mid;elser = midmid;}Point tt = getPoint(l);ans = tt.distance(st) + getdist(tt);l = pi;r = 2 * pi;while (r - l >= eps){
mid = (l + r) / 2;midmid = (mid + r) / 2;p1 = getPoint(mid);p2 = getPoint(midmid);dis1 = p1.distance(st) + getdist(p1);dis2 = p2.distance(st) + getdist(p2);if (dis1 > dis2)l = mid;elser = midmid;}tt = getPoint(l);ans = min(ans, tt.distance(st) + getdist(tt));return ans;
}int main()
{
while (cin >> st.x >> st.y){
if (sgn(st.x) == 0 && sgn(st.y) == 0)break;cin >> c1.x >> c1.y >> r;cin >> t1.x >> t1.y >> t2.x >> t2.y;printf("%.2f\n", solve());}return 0;
}