Closest Points Problem

Tuong_Le · September 19, 2020, 12:24pm

Xin chào mọi người, chẳng là em đang làm bài tính 2 điểm ngắn nhất. Mà em làm rồi thì không biết sai chỗ nào, mọi người giúp em với

#include "pch.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
//binary search
int binarySearch(vector<int> a, double key, int left, int right)
{
	int mid = (left + right) / 2;
	if ((mid == left && a[mid] > key) || (mid == right && a[mid] < key) || (a[mid] == key)) return mid;
	else if ((a[mid] > key && a[mid - 1] < key) || (a[mid]<key && a[mid + 1]>key)) return mid;
	else if (a[mid] > key) return binarySearch(a, key, left, mid);
	else if (a[mid] < key) return binarySearch(a, key, mid + 1, right);
}
// 3 way quick sort
void partition(vector <int> &a, vector <int> &b, int l, int r, int &i, int &j)
{
	i = l - 1, j = r;
	int p = l - 1, q = r;
	int v = a[r];
	while (true)
	{
		while (a[++i] < v);
		while (v < a[--j])
			if (j == l)
				break;
		if (i >= j) break;
		swap(a[i], a[j]);
		swap(b[i], b[j]);
		if (a[i] == v)
		{
			p++;
			swap(a[p], a[i]);
			swap(b[p], b[i]);
		}
		if (a[j] == v)
		{
			q--;
			swap(a[j], a[q]);
			swap(b[j], b[q]);
		}
	}
	swap(a[i], a[r]);
	swap(b[i], b[r]);
	j = i - 1;
	for (int k = l; k < p; k++, j--)
	{
		swap(a[k], a[j]);
		swap(b[k], b[j]);
	}
	i = i + 1;
	for (int k = r - 1; k > q; k--, i++)
	{
		swap(a[i], a[k]);
		swap(b[i], b[k]);
	}
}
void quicksort(vector <int> &a, vector<int> &b, int l, int r)
{
	if (r <= l) return;
	int i, j;
	partition(a, b, l, r, i, j);
	quicksort(a, b, l, j);
	quicksort(a, b, i, r);
}

double part_minimal_distance(vector<int> &x, vector<int> &y, int left, int right)
{
	if (right - left == 2)
	{
		double a = sqrt(pow(x[left] - x[right], 2) + pow(y[left] - y[right], 2));
		double b = sqrt(pow(x[left+1] - x[right], 2) + pow(y[left+1] - y[right], 2));
		double c = sqrt(pow(x[left] - x[right-1], 2) + pow(y[left] - y[right-1], 2));
		double min = a > b ? b : a;
		return min > c ? c : min;
	}
	else if (right - left == 1)
	{
		return sqrt(pow(x[left] - x[right], 2) + pow(y[left] - y[right], 2));
	}
	if (right == left) return -1;
	int mid = (left + right) / 2;
	double d1 = part_minimal_distance(x, y, left, mid);
	double d2 = part_minimal_distance(x, y, mid + 1, right);
	double min = d1 > d2 ? d2 : d1;
	//
	int l = binarySearch(x, x[mid] - min, left, right);
	int r = binarySearch(x, x[mid] + min, left, right);
	quicksort(y, x, l, r);
	double min2 = 0;
	for (int i = l; i <= r; i++)
	{
		for (int j = 1; j <= 7; j++)
		{
			if (i+j > r) break;
			double d = sqrt(pow(x[i] - x[i+j], 2) + pow(y[i] - y[i+j], 2));
			if (min2 == 0) min2 = d;
			else min2 = min2 > d ? d : min2;
		}
	}
	return min > min2 ? min2 : min;
}
double minimal_distance(vector<int> &x, vector<int> &y) {
	//write your code here
	quicksort(x, y, 0, x.size()-1);
	return part_minimal_distance(x, y, 0, x.size() - 1);
}
int main() {
	size_t n;
	cin >> n;
	vector<int> x(n);
	vector<int> y(n);
	for (size_t i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	cout << fixed;
	cout << setprecision(9) << minimal_distance(x, y) << "\n";
}

Thuật toán của em làm theo hướng dẫn này:

Em nghĩ rằng code em nó sai chỗ này:

int l = binarySearch(x, x[mid] - min, left, right);
int r = binarySearch(x, x[mid] + min, left, right);
quicksort(y, x, l, r);
double min2 = 0;
for (int i = l; i <= r; i++)
{
	for (int j = 1; j <= 7; j++)
	{
		if (i+j > r) break;
		double d = sqrt(pow(x[i] - x[i+j], 2) + pow(y[i] - y[i+j], 2));
		if (min2 == 0) min2 = d;
		else min2 = min2 > d ? d : min2;
	}
}
return min > min2 ? min2 : min;

noname00 · September 19, 2020, 12:24pm

merged to the #1 post by noname00

Tuong_Le · September 19, 2020, 8:25am

Boo hoo em tìm ra lỗi sai rồi

if (min2 == 0) return min;
return min > min2 ? min2 : min;

Nhưng mà nó lại bị time limit exceeded ở test case thứ 17/23 Làm sao đây

noname00 · September 19, 2020, 12:33pm

Góp ý về đoạn code:

Bạn sử dụng ternary operator để tìm min khá nhiều lần. Tại sao bạn không thử viết hàm tính min?
Hàm binarySearch bạn đang sử dụng đệ quy. Bạn nên khử đệ quy để giảm bớt số lần gọi hàm.
Tính toán với số thực cũng mất thời gian. Có lẽ không nên tính khoảng cách giữa 2 điểm ngay mà có thể tính bình phương khoảng cách (giá trị này vẫn chỉ là số nguyên) rồi so sánh. Hơn nữa, bước tính khoảng cách lặp lại khá nhiều lần.

long long sqr_distance(int x1, int y1, int x2, int y2) {
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    // bỏ luôn pow đi, vì hàm pow trả về số thực
}

...
// thử sử dụng
double d2 = sqr_distance(x[i], y[i], x[i+j], y[i+j]); // d^2

rogp10 · September 19, 2020, 12:45pm

Với lại dùng struct luôn chứ parallel array là miscache gấp đôi, vì mảng tung độ và mảng hoành độ rất xa nhau.

Bình phương thì dùng sqr() viết cũng gọn nữa.

Tuong_Le · September 19, 2020, 1:06pm

Trước hết, em xin cảm ơn sự góp ý tinh tế của 2 anh, em cũng đã sửa code được một vài ý. Em vẫn chưa sửa được hàm binarySearch. Và cũng giải thích vì sao em lại dùng vector chứ ko phải là Struct hay Class, là vì đề bài yêu cầu vậy nên em làm vậy :)))).
Nhưng mà sau khi sửa xong các phép tính thì hình như nó vẫn chưa chạm đến vấn đề cốt lõi của bài làm của em. Vì nó mất 3,99/2,00 (trước đó cũng vậy). Boohoo mong các anh nhận xét thêm về phần thuật toán nữa. Em cảm ơn nhiều lắm.

#include "pch.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
//binary search
int binarySearch(vector<int> a, double key, int left, int right)
{
	int mid = (left + right) / 2;
	if ((mid == left && a[mid] > key) || (mid == right && a[mid] < key) || (a[mid] == key)) return mid;
	else if ((a[mid] > key && a[mid - 1] < key) || (a[mid]<key && a[mid + 1]>key)) return mid;
	else if (a[mid] > key) return binarySearch(a, key, left, mid);
	else if (a[mid] < key) return binarySearch(a, key, mid + 1, right);
}
// 3 way quick sort
void partition(vector <int> &a, vector <int> &b, int l, int r, int &i, int &j)
{
	i = l - 1, j = r;
	int p = l - 1, q = r;
	int v = a[r];
	while (true)
	{
		while (a[++i] < v);
		while (v < a[--j])
			if (j == l)
				break;
		if (i >= j) break;
		swap(a[i], a[j]);
		swap(b[i], b[j]);
		if (a[i] == v)
		{
			p++;
			swap(a[p], a[i]);
			swap(b[p], b[i]);
		}
		if (a[j] == v)
		{
			q--;
			swap(a[j], a[q]);
			swap(b[j], b[q]);
		}
	}
	swap(a[i], a[r]);
	swap(b[i], b[r]);
	j = i - 1;
	for (int k = l; k < p; k++, j--)
	{
		swap(a[k], a[j]);
		swap(b[k], b[j]);
	}
	i = i + 1;
	for (int k = r - 1; k > q; k--, i++)
	{
		swap(a[i], a[k]);
		swap(b[i], b[k]);
	}
}
void quicksort(vector <int> &a, vector<int> &b, int l, int r)
{
	if (r <= l) return;
	int i, j;
	partition(a, b, l, r, i, j);
	quicksort(a, b, l, j);
	quicksort(a, b, i, r);
}
long long sqr_distance(int x1, int x2, int y1, int y2)
{
	return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
long long minFunc(double a, double b)
{
	return a > b ? b : a;
}
long long part_minimal_distance(vector<int> &x, vector<int> &y, int left, int right)
{
	if (right - left == 2)
	{
		long long a = sqr_distance(x[left], x[right], y[left], y[right]);
		long long b = sqr_distance(x[left + 1], x[right], y[left + 1], y[right]);
		long long c = sqr_distance(x[left], x[right - 1], y[left], y[right - 1]);
		long long min = minFunc(a,b);
		return minFunc(min,c);
	}
	else if (right - left == 1)
	{
		return sqr_distance(x[left], x[right], y[left], y[right]);
	}
	else if (right == left) return -1;
	int mid = (left + right) / 2;
	long long d1 = part_minimal_distance(x, y, left, mid);
	long long d2 = part_minimal_distance(x, y, mid + 1, right);
	long long min = minFunc(d1,d2);
	//find min between 2 part
	int l = binarySearch(x, x[mid] - sqrt(min), left, right);
	int r = binarySearch(x, x[mid] + sqrt(min), left, right);
	quicksort(y, x, l, r);
	long long min2 = 0;
	for (int i = l; i <= r; i++)
	{
		for (int j = 1; j <= 7; j++)
		{
			if (i+j > r) break;
			double d = sqr_distance(x[i], x[i + j], y[i], y[i + j]);
			if (min2 == 0) min2 = d;
			else min2 = minFunc(min2,d);
		}
	}
	if (min2 == 0) return min;
	return minFunc(min,min2);
}
double minimal_distance(vector<int> &x, vector<int> &y) {
	//write your code here
	quicksort(x, y, 0, x.size()-1);
	return part_minimal_distance(x, y, 0, x.size() - 1);
}
int main() {
	size_t n;
	cin >> n;
	vector<int> x(n);
	vector<int> y(n);
	for (size_t i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	cout << fixed;
	cout << setprecision(9) << sqrt(minimal_distance(x, y)) << "\n";
}

rogp10 · September 19, 2020, 1:52pm

“Chỉ cần xét 7 điểm liền kề” bạn có thấy lạ không (sao có 7 điểm vậy - thật sự không dễ)

Khẳng định này dựa vào việc các điểm ĐÃ xếp theo thứ tự tung độ ko giảm. Vậy cái chính là tung độ không giảm, hay vấn đề là chia hai bờ kiểu gì để bảo toàn thứ tự của tung độ

Tuong_Le · September 19, 2020, 1:51pm

Em ko thấy lạ, mà em hiểu chết liền luôn. Còn ý sau của anh, em cũng chưa hiểu lắm em nên làm gì nữa.

rogp10 · September 19, 2020, 2:59pm

Stable partition đúng là O(N) time như trong đó nhưng còn thêm O(N) mem nữa lôi phần tử bên phải ra ngoài, dồn mảng, chép lại.

Tuong_Le · September 19, 2020, 3:17pm

Thế là vấn đề nằm ở chỗ QuickSort chiếm nhiều thời gian hả anh, em nên giải quyết thế nào cho gọn hả anh?

rogp10 · September 19, 2020, 4:14pm

Quên vụ sắp xếp theo hoành độ đi.

Còn xét vùng giáp ranh thì tung độ xếp tăng dần, rồi bạn làm như bài trộn mảng ấy.

p/s: chỉ cần xét khoảng cách 1 điểm với lần lượt 6 điểm kế tiếp.

Tuong_Le · September 19, 2020, 4:20pm

Nếu làm thế thì sẽ có vấn đề là không thể tính được l,r. vì l,r hoàn toàn phụ thuộc vào cách x có sắp xếp hay không. Có cách nào khác để tính l, r không ạ?

rogp10 · September 19, 2020, 4:31pm

Không sắp xếp theo x rồi mà Chỉ cần |x - p_x| < d là xử lí được.

Tiếp theo là làm sao có 7 điểm (1+6) để thao tác?

Tuong_Le · September 19, 2020, 4:55pm

Khoan nha, out trình rồi, để nay suy nghĩ rồi mai em hỏi tiếp nha, cảm ơn anh đã dành thời gian nhe. Nhưng mà cách của em ko cứu được hả anh, test case 17/23 rồi
p/s em thấy rồi nha :v circular buffer.
Em hiểu rồi, có phải nó cố tình chỉ mình cách không thể hoàn thành được test case, song vẫn gợi ý 1 cách để giải quyết phần test case còn lại như trong exercise break thứ 2 không? :v

rogp10 · September 21, 2020, 2:09am

Khi n lớn dần thì big-O sẽ thể hiện rõ, nên input lớn là phân biệt được.

Vì lúc bạn chia mảng đã có buffer rồi

Mà 15 điểm trở xuống thì theo cách cũ nhanh hơn. Có thể là 25 - 30 luôn vì phải chép đi chép lại.