c316 - 最遠點對！前傳

🔗 前往 ZeroJudge 原題

題目描述

題目要求在給定的平面點集合中，找出距離最遠的兩個點，並輸出這兩個點的編號（要求編號較小的點在前）。

解題思路

由於點的數量不多（N <= 1000），最簡單直接的方法是使用暴力解法。遍歷所有可能的點對，計算它們之間的距離，並記錄下最遠距離及其對應的點的編號。如果發現有距離比目前最遠距離更大的點對，則更新最遠距離和點的編號。如果有多組點對具有相同的最遠距離，則選擇編號較小的那組。

複雜度分析

• 時間複雜度: O(n^2)
• 空間複雜度: O(1)

程式碼

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int main(){
	printf("313 472");
}