Bài toán Clustering: Cho mặt phẳng tọa độ Oxy, có n điểm và số nguyên k là số nhóm điểm, tính d sao cho d có giá trị lớn nhất và bất kỳ 2 điểm nào thuộc 2 nhóm khác nhau đều có khoảng cách ngắn nhất là d.
Ví dụ:
Các điểm trên mặt phẳng được chia làm 3 nhóm và khoảng cách ngắn nhất thỏa mãn là khoảng cách giữa 2 điểm (4,6) và (9,8).
Đây là bài giải của em:
// Week5Problem2.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include "pch.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <cmath>
using namespace std;
struct DisjointSetsElement {
int size, parent, rank;
DisjointSetsElement(int size = 0, int parent = -1, int rank = 0) :
size(size), parent(parent), rank(rank) {}
};
struct DisjointSets {
int size;
int max_table_size;
vector <DisjointSetsElement> sets;
DisjointSets(int size) : size(size), max_table_size(0), sets(size) {
for (int i = 0; i < size; i++)
sets[i].parent = i;
}
int getParent(int table) {
// find parent and compress path
int result = table;
while (sets[result].parent != result)
{
result = sets[result].parent;
}
return result;
}
void merge(int destination, int source) {
int realDestination = getParent(destination);
int realSource = getParent(source);
if (realDestination != realSource) {
// merge two components
// use union by rank heuristic
// update max_table_size
if (sets[realSource].rank > sets[realDestination].rank)
{
sets[realDestination].parent = realSource;
sets[realSource].size += sets[realDestination].size;
sets[realDestination].size = 0;
if (max_table_size < sets[realSource].size) max_table_size = sets[realSource].size;
}
else
{
sets[realSource].parent = realDestination;
sets[realDestination].size += sets[realSource].size;
sets[realSource].size = 0;
if (max_table_size < sets[realDestination].size) max_table_size = sets[realDestination].size;
if (sets[realSource].rank == sets[realDestination].rank)
{
sets[realDestination].rank = sets[realDestination].rank + 1;
}
}
}
}
};
class minPriorityQueue {
private:
vector<pair<double, int>> data_;
int parent(int i)
{
return (i - 1) / 2;
}
int leftChild(int i)
{
return 2 * i + 1;
}
int rightChild(int i)
{
return 2 * i + 2;
}
void siftDown(int i)
{
if (i > (data_.size() - 2) / 2)
return;
int minIndex = i;
int l = leftChild(i);
if (l <= data_.size() - 1 && data_[l].first < data_[minIndex].first)
minIndex = l;
int r = rightChild(i);
if (r <= data_.size() - 1 && data_[r].first < data_[minIndex].first)
minIndex = r;
if (i != minIndex)
{
swap(data_[i], data_[minIndex]);
siftDown(minIndex);
}
}
void siftUp(int i)
{
while (i > 0 && data_[parent(i)].first >= data_[i].first)
{
swap(data_[i], data_[parent(i)]);
i = parent(i);
}
}
public:
void push(pair<double, int> i)
{
data_.push_back(i);
siftUp(data_.size() - 1);
}
pair<double, int> extractMin()
{
pair<double, int> result = data_[0];
swap(data_[0], data_[data_.size() - 1]);
data_.pop_back();
if (data_.size() != 0)
siftDown(0);
return result;
}
bool empty()
{
if (data_.size() == 0)
return 1;
return 0;
}
void changePriority(double distance, int neighbour)
{
for (int i = 0; i < data_.size(); i++)
{
if (data_[i].second == neighbour)
{
data_[i].first = distance;
siftUp(i);
siftDown(i);
return;
}
}
}
};
double clustering(vector<int> x, vector<int> y, int k) {
//write your code here
//if k == 1, there're only one cluster
if (k == 1) return 0;
minPriorityQueue heap;
vector<double> distance;
vector<pair<int, int>> vertexs;
int numbedge = 0;
for (int i = 0; i < x.size(); i++)
{
for (int j = i + 1; j < x.size(); j++)
{
double distance = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
heap.push(make_pair(distance, numbedge));
numbedge++;
vertexs.push_back(make_pair(i,j));
}
}
DisjointSets tables(x.size());
int groups = x.size();
pair<double, int> current;
pair<int, int> vertex;
while (!heap.empty())
{
current = heap.extractMin();
vertex = vertexs[current.second];
if (groups == k)
break;
// if 2 points are the same group, skip it
if (tables.getParent(vertex.first) == tables.getParent(vertex.second))
continue;
// union 2 point together
tables.merge(vertex.first, vertex.second);
groups--;
}
return current.first;
}
int main() {
size_t n;
int k;
cin >> n;
vector<int> x(n), y(n);
for (size_t i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
cin >> k;
cout << setprecision(10) << clustering(x, y, k) << endl;
}
Trong phần giải thuật, em có sử dụng 2 Function min priority queue và disjoint set. Cả 2 function này đều chạy ổn, vì em chỉ copy lại hàm của bài tập trước, và nó đều đã pass được hết test case.
Ý tưởng giải bài toán là tính khoảng cách tất cả các đoạn thẳng, và đưa vào min priority queue. Trong đó có lưu distance value và địa chỉ được lưu trong vector vertexs tương ứng với 2 điểm. Sau đó dùng disjoint sets Union by rank 2 điểm lại với nhau, cho đến khi chỉ còn lại k nhóm. Rồi return distance tiếp theo. Tuy vậy, có lẽ em đã không để ý đến trường hợp nào đó còn sót, nên bài này fall ở test case 9/40. Mong các anh chị xem và gợi ý giúp em, em xin cảm ơn nhiều. :3
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?