题目链接:http://codeforces.com/gym/101650/attachments
Time Limit: 2000MS Memory Limit: 65536K
Description
Feng shui is the ancient Chinese practice of placement and arrangement of space to achieve harmony with the environment. George has recently got interested in it, and now wants to apply it to his home and bring harmony to it.
There is a practice which says that bare floor is bad for living area since spiritual energy drains through it, so George purchased two similar round-shaped carpets (feng shui says that straight lines and sharp corners must be avoided). Unfortunately, he is unable to cover the floor entirely since the room has shape of a convex polygon. But he still wants to minimize the uncovered area by selecting the best placing for his carpets, and asks you to help.
You need to place two carpets in the room so that the total area covered by both carpets is maximal possible. The carpets may overlap, but they may not be cut or folded (including cutting or folding along the floor border) — feng shui tells to avoid straight lines.
Input
The first line of the input file contains two integer numbers n and r — the number of corners in George’s room (3 ≤ n ≤ 100) and the radius of the carpets (1 ≤ r ≤ 1000, both carpets have the same radius). The following n lines contain two integers xi and yi each — coordinates of the i-th corner (−1000 ≤ xi, yi≤ 1000). Coordinates of all corners are different, and adjacent walls of the room are not collinear. The corners are listed in clockwise order.
Output
Write four numbers x1, y1, x2, y2 to the output file, where (x1, y1) and (x2, y2) denote the spots where carpet centers should be placed. Coordinates must be precise up to 4 digits after the decimal point.
If there are multiple optimal placements available, return any of them. The input data guarantees that at least one solution exists.
Sample Input
5 2
-2 0
-5 3
0 8
7 3
5 0
4 3
0 0
0 8
10 8
10 0
Sample Output
-2 3 3 2.5
3 5 7 3
Hint
Problem solving report:
Description: 给一个凸多边形围成的房子,顺时针给出点,再给两块半径为r的地毯,要求地毯覆盖面积最大且地毯不能切割或折叠,求地毯最大面积覆盖的时候地毯的圆心坐标,任意输出一组解。
Problem solving: 首先将房子所有边向内移动r,得到一个凸包,凸包上的最远点对即答案之一,暴力枚举最远点。
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const double eps = 1e-8;
typedef struct point {
double x, y;
}vect;
point p[MAXN];
struct line {
vect p;
point u, v;
}Sline[MAXN];
vect operator - (const point a, const point b) {
return (vect){a.x - b.x, a.y - b.y};
}
int pnz(double x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
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 Cross(const vect a, const vect b) {
return a.x * b.y - a.y * b.x;
}
int Onleft(const point p, const line l) {
return pnz(Cross(l.p, p - l.u));
}
point Inter(const line a, const line b) {
double t = Cross(b.p, a.u - b.u) / Cross(a.p, b.p);
return (point){a.u.x + t * a.p.x, a.u.y + t * a.p.y};
}
void Mobile(line l[], int n, int r) {
for (int i = 0; i < n; i++) {
double dis = dist(l[i].u, l[i].v);
double dx = (l[i].v.y - l[i].u.y) / dis * r;
double dy = (l[i].v.x - l[i].u.x) / dis * r;
l[i].u.x -= dx, l[i].u.y += dy;
l[i].v.x -= dx, l[i].v.y += dy;
}
}
void Farthest(point p[], int n) {
int x = 0, y = 0;
double max_ = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double dis = dist(p[i], p[j]);
if (pnz(dis - max_) > 0) {
max_ = dis;
x = i, y = j;
}
}
}
printf("%.5f %.5f %.5f %.5f\n", p[x].x, p[x].y, p[y].x, p[y].y);
}
void Halfplane(int n) {
point Spt[n];
int Q[n] = {0};
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
while (l < r && Onleft(Spt[r - 1], Sline[i]) < 0)
r--;
while (l < r && Onleft(Spt[l], Sline[i]) < 0)
l++;
Q[++r] = i;
if (!pnz(Cross(Sline[i].p, Sline[Q[r - 1]].p))) {
r--;
if (Onleft(Sline[i].u, Sline[Q[r]]) > 0)
Q[r] = i;
}
if (l < r) Spt[r - 1] = Inter(Sline[Q[r]], Sline[Q[r - 1]]);
}
while (l < r && Onleft(Spt[r - 1], Sline[Q[l]]) < 0)
r--;
while (l < r && Onleft(Spt[l], Sline[Q[r]]) < 0)
l++;
Spt[r] = Inter(Sline[Q[l]], Sline[Q[r]]);
Farthest(Spt + l, r - l + 1);
}
int main() {
int n, r;
while (~scanf("%d%d", &n, &r)) {
for (int i = n - 1; i >= 0; i--)
scanf("%lf%lf", &p[i].x, &p[i].y);
p[n] = p[0];
for (int i = 0; i < n; i++)
Sline[i] = (line){p[i + 1] - p[i], p[i], p[i + 1]};
Mobile(Sline, n, r);
Halfplane(n);
}
return 0;
}