/* pku_半平面交算法的一个应用(两圆覆盖凸多边形,只能是凸多边形) 具体做法是,把多边形的每条边向内平移r单位长度,用这些线段所在直线和原多边形作半平面交,得到的区域就是半径为r的圆放入多边形的可行域。可以证明这个区域一定是凸的,或者退化为一条线段,或一个点。那么,我们就可以在这个区域上求最远点对啦。 */ #include #include #include #include #include using namespace std; #define maxn 110 #define eps 1e-8 #define inf 0xffffff struct Nodes { double x, y; }; struct Set { int nn; Nodes p[300]; }; int n; Set src; double cross(Nodes p1, Nodes p2, Nodes p3) { return ((p2.x - p1.x)*(p3.y - p1.y)-(p2.y - p1.y)*(p3.x - p1.x)); } double sqr(double x) { return x*x; } double dis(Nodes p1, Nodes p2) { return sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y)); } void Getline(Nodes p1, Nodes p2, double &a, double &b, double &c) { a = p2.y - p1.y; b = p1.x - p2.x; c = p1.y * (p2.x - p1.x) - p1.x * (p2.y - p1.y); } Nodes get_crossp(double a1, double b1, double c1, double a2, double b2, double c2) { Nodes ret; ret.x = -(c1 * b2 - b1 * c2) / (a1 * b2 - a2 * b1); ret.y = -(a1 * c2 - a2 * c1) / (a1 * b2 - a2 * b1); return ret; } int isequal(Nodes p1, Nodes p2) { if (fabs(p1.x - p2.x) < eps && fabs(p1.y - p2.y) < eps)return 1; return 0; } Set cut(Nodes p1, Nodes p2, Set s) { int i, j, k; double t1, t2, a1, b1, c1, a2, b2, c2; Nodes crossp; Set ret; ret.nn = 0; for (i = 0; i < s.nn; i++) { t1 = cross(p1, p2, s.p[i]); t2 = cross(p1, p2, s.p[i + 1]); if (t1 < eps && t2 < eps) { ret.p[ret.nn++] = s.p[i]; ret.p[ret.nn++] = s.p[i + 1]; } else if (t1 > eps && t2 > eps) { continue; } else { Getline(p1, p2, a1, b1, c1); Getline(s.p[i], s.p[i + 1], a2, b2, c2); crossp = get_crossp(a1, b1, c1, a2, b2, c2); if (t1 < eps) { ret.p[ret.nn++] = s.p[i]; ret.p[ret.nn++] = crossp; } else { ret.p[ret.nn++] = crossp; ret.p[ret.nn++] = s.p[i + 1]; } } } if (ret.nn == 0)return ret; j = 1; for (i = 1; i < ret.nn; i++) { if (isequal(ret.p[i - 1], ret.p[i]))continue; ret.p[j++] = ret.p[i]; } ret.nn = j; if (ret.nn != 1 && isequal(ret.p[ret.nn - 1], ret.p[0]))ret.nn--; ret.p[ret.nn] = ret.p[0]; return ret; } int main() { int i, j, k, r; Set s; Nodes p1, p2; double dx, dy; double len, maxdis; while (scanf("%d%d", &n, &r) != EOF) { src.nn = n; for (i = 0; i < src.nn; i++) { scanf("%lf%lf", &src.p[i].x, &src.p[i].y); } src.p[src.nn] = src.p[0]; s = src; for (i = 0; i < src.nn; i++) { dx = src.p[i + 1].x - src.p[i].x; dy = src.p[i + 1].y - src.p[i].y; len = dis(src.p[i + 1], src.p[i]); p1.x = src.p[i].x + dy * r / len; p1.y = src.p[i].y - dx * r / len; p2.x = src.p[i + 1].x + dy * r / len; p2.y = src.p[i + 1].y - dx * r / len; s = cut(p1, p2, s); } maxdis = -inf * 1.0; for (i = 0; i < s.nn; i++) { for (j = i; j < s.nn; j++) { len = dis(s.p[i], s.p[j]); if (len > maxdis) { maxdis = len; p1 = s.p[i]; p2 = s.p[j]; } } } printf("%.4lf %.4lf %.4lf %.4lf\n", p1.x, p1.y, p2.x, p2.y); } return 0; }