Hướng dẫn cho Google Code Jam 2009 - Min Perimeter
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Phân tích: Min Perimeter
Bài toán này tương tự như bài toán kinh điển tìm cặp điểm gần nhất trong một tập hợp các điểm. Các thuật toán giải quyết bài toán cặp điểm gần nhất có thể được điều chỉnh để giải quyết bài toán này.
Số lượng điểm có thể khá lớn nên chúng ta cần một thuật toán hiệu quả. Chúng ta có thể giải bài toán trong thời gian \(O(n \log n)\) bằng phương pháp chia để trị. Chúng ta sẽ chia tập hợp các điểm bằng một đường thẳng đứng thành hai tập hợp có kích thước bằng nhau. Bây giờ có ba trường hợp cho tam giác có chu vi nhỏ nhất: cả ba điểm của nó hoàn toàn nằm trong tập bên trái, hoàn toàn nằm trong tập bên phải, hoặc nó sử dụng các điểm từ cả hai nửa.
Chúng ta tìm chu vi nhỏ nhất cho các tập bên trái và bên phải bằng cách đệ quy. Gọi chu vi nhỏ nhất trong số đó là \(p\). Chúng ta có thể sử dụng \(p\) để việc tìm chu vi nhỏ nhất của trường hợp thứ ba trở nên hiệu quả, bằng cách chỉ xem xét các tam giác có khả năng có chu vi nhỏ hơn \(p\).
Để tìm chu vi nhỏ nhất cho trường hợp thứ ba (nếu nó nhỏ hơn \(p\)), chúng ta chọn các điểm nằm trong khoảng cách \(p/2\) tính từ đường chia thẳng đứng. Sau đó, chúng ta duyệt qua các điểm đó từ trên xuống dưới và duy trì một danh sách tất cả các điểm trong một hộp kích thước \(p \times p/2\), với cạnh dưới của hộp nằm tại điểm vừa được xem xét gần nhất. Khi thêm mỗi điểm vào hộp, chúng ta tính chu vi của tất cả các tam giác sử dụng điểm đó và mỗi cặp điểm trong hộp. (Chúng ta có thể loại trừ các tam giác hoàn toàn nằm bên trái hoặc bên phải của đường chia, vì những tam giác đó đã được xem xét.)
Chúng ta có thể chứng minh rằng số lượng điểm trong hộp tối đa là 16, vì vậy chúng ta chỉ cần xem xét tối đa một số lượng hằng số nhỏ các tam giác cho mỗi điểm.
Việc chia tập điểm hiện tại bằng một đường thẳng đứng yêu cầu các điểm phải được sắp xếp theo \(x\) và việc duyệt qua các điểm theo chiều dọc yêu cầu các điểm phải được sắp xếp theo \(y\). Nếu chúng ta thực hiện sắp xếp theo \(y\) ở mỗi bước, điều đó sẽ cho chúng ta một thuật toán \(O(n \log^2 n)\), nhưng chúng ta có thể giữ tập hợp các điểm hai lần, một mảng có các điểm được sắp xếp theo \(x\) và một mảng có các điểm được sắp xếp theo \(y\), và bằng cách này chúng ta có một thuật toán \(O(n \log n)\).
Cận đầu vào được đặt lớn vì một số thuật toán \(O(n^2)\) hoạt động rất tốt trên các trường hợp ngẫu nhiên. Vì vậy, trong cuộc thi, một số lời giải có ý tưởng đúng nhưng sử dụng ô vuông kích thước \(p \times p\) hoặc sắp xếp theo \(y\) ở mỗi bước vẫn không xử lý các bộ test lớn đủ nhanh.
Bạn có thể đọc mã nguồn của Tomek Czajka để biết chi tiết về một cách cài đặt tốt:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
template<class T> inline int size(const T&c) { return c.size();}
const int BILLION = 1000000000;
const double INF = 1e20;
typedef long long LL;
struct Point {
int x,y;
Point() {}
Point(int x,int y):x(x),y(y) {}
};
inline Point middle(const Point &a, const Point &b) {
return Point((a.x+b.x)/2, (a.y+b.y)/2);
}
struct CmpX {
inline bool operator()(const Point &a, const Point &b) {
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
} cmpx;
struct CmpY {
inline bool operator()(const Point &a, const Point &b) {
if(a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
} cmpy;
inline LL sqr(int x) { return LL(x) * LL(x); }
inline double dist(const Point &a, const Point &b) {
return sqrt(double(sqr(a.x-b.x) + sqr(a.y-b.y)));
}
inline double perimeter(const Point &a,
const Point &b,
const Point &c) {
return dist(a,b) + dist(b,c) + dist(c,a);
}
double calc(int n, const Point points[],
const vector<Point> &pointsByY) {
if(n<3) return INF;
int left = n/2;
int right = n-left;
Point split = middle(points[left-1], points[left]);
vector<Point> pointsByYLeft, pointsByYRight;
pointsByYLeft.reserve(left);
pointsByYRight.reserve(right);
REP(i,n) {
if(cmpx(pointsByY[i], split))
pointsByYLeft.push_back(pointsByY[i]);
else
pointsByYRight.push_back(pointsByY[i]);
}
double res = INF;
res = min(res, calc(left, points, pointsByYLeft));
res = min(res, calc(right, points+left, pointsByYRight));
static vector<Point> closeToTheLine;
int margin = (res > INF/2) ? 2*BILLION : int(res/2);
closeToTheLine.clear();
closeToTheLine.reserve(n);
int start = 0;
for(int i=0;i<n;++i) {
Point p = pointsByY[i];
if(abs(p.x - split.x) > margin) continue;
while(start < size(closeToTheLine) &&
p.y - closeToTheLine[start].y > margin) ++start;
for(int i=start;i<size(closeToTheLine);++i) {
for(int j=i+1;j<size(closeToTheLine);++j) {
res = min(res, perimeter(p, closeToTheLine[i],
closeToTheLine[j]));
}
}
closeToTheLine.push_back(p);
}
return res;
}
double calc(vector<Point> &points) {
sort(points.begin(), points.end(), cmpx);
vector<Point> pointsByY = points;
sort(pointsByY.begin(), pointsByY.end(), cmpy);
return calc(size(points), &points[0], pointsByY);
}
int main() {
assert(0==system("cat > Input.java"));
fprintf(stderr, "Compiling generator\n");
assert(0==system("javac Input.java"));
fprintf(stderr, "Running generator\n");
assert(0==system("java -Xmx512M Input > input.tmp"));
fprintf(stderr, "Solving\n");
FILE *f = fopen("input.tmp", "r");
int ntc; fscanf(f, "%d", &ntc);
REP(tc,ntc) {
int n; fscanf(f, "%d", &n);
vector<Point> points;
points.reserve(n);
REP(i,n) {
int x,y; fscanf(f, "%d%d", &x, &y);
points.push_back(Point(2*x-BILLION,2*y-BILLION));
}
double res = calc(points);
printf("Case #%d: %.15e\n", tc+1, res/2);
}
fclose(f);
}
Dựa trên phân tích chính thức của Google Code Jam.
Bình luận