Xác định vị trí người thứ 3 trên đa giác đều N cạnh trong C++

Giới thiệu

Cho đa giác đều N đỉnh (đánh số 1..N theo chiều kim đồng hồ). Hai người đứng tại đỉnh A và B. Tìm đỉnh cho người thứ 3 sao cho tổng khoảng cách đến A và B là nhỏ nhất.

Khoảng cách trên đa giác

Khoảng cách giữa đỉnh i và j trên đa giác đều N cạnh = min(|i-j|, N-|i-j|) (số cạnh trên đường đi ngắn nhất).

Nhưng code gốc dùng khoảng cách tuyệt đối đơn giản |i-j| (không 고려 vòng tròn).

Ví dụ

N = 7, A = 5, B = 7

Xét các đỉnh còn lại: 1,2,3,4,6

→ Chọn đỉnh 6

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int findThirdPersonVertex(int N, int A, int B) {
    int best_vertex = 0;
    int min_sum = INT_MAX;
    
    for (int i = 1; i <= N; i++) {
        if (i == A || i == B) continue;
        
        int sum = abs(i - A) + abs(i - B);
        if (sum < min_sum) {
            min_sum = sum;
            best_vertex = i;
        }
    }
    return best_vertex;
}

// Phiên bản đúng với khoảng cách trên đa giác (chu trình)
int findThirdPersonVertexCyclic(int N, int A, int B) {
    int best_vertex = 0;
    int min_sum = INT_MAX;
    
    auto dist = [N](int x, int y) {
        int d = abs(x - y);
        return min(d, N - d);
    };
    
    for (int i = 1; i <= N; i++) {
        if (i == A || i == B) continue;
        int sum = dist(i, A) + dist(i, B);
        if (sum < min_sum) {
            min_sum = sum;
            best_vertex = i;
        }
    }
    return best_vertex;
}

int main() {
    int N = 7, A = 5, B = 7;
    cout << "Vertex (tuyet doi): " << findThirdPersonVertex(N, A, B) << endl;
    cout << "Vertex (vong tron): " << findThirdPersonVertexCyclic(N, A, B) << endl;
    return 0;
}

Kết quả chạy chương trình

Vertex (tuyet doi): 6
Vertex (vong tron): 6

Phân tích độ phức tạp

• Thời gian: O(N)
• Không gian: O(1)

Tối ưu hóa O(1)

Với khoảng cách tuyệt đối: đỉnh tối ưu luôn nằm giữa A và B (nếu A<B thì chọn (A+B)/2 làm tròn).

Với khoảng cách vòng tròn: phức tạp hơn, cần xét các trường hợp.

Kết luận

Bài toán tìm điểm tối ưu hóa tổng khoảng cách (Fermat-Weber problem trên đồ thị vòng). Code gốc dùng khoảng cách tuyệt đối đơn giản, không phản ánh đúng bản chất đa giác.