[TIOJ] 1105. H.PS3
題目連結: http://tioj.infor.org/problems/1105 如果我沒猜錯的話，這題應該可以用旋轉卡尺做到$O(n log n)$，但是我實在不熟，加上本題範圍$O(n^2)$就可以過了，所以我就直接寫個裸裸的做法了 #include <bits/stdc++.h>
using namespace std;
#define N 3000
typedef pair<int,int> PII;
#define X first
#define Y second
#define DIS(a,b) ((arr[a].X-arr[b].X)*(arr[a].X-arr[b].X)+(arr[a].Y-arr[b].Y)*(arr[a].Y-arr[b].Y))
PII arr[N+5];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin>>n;
while(n>0){
int a=0, b=0;
for(int i=0;i<n;i++) cin>>arr[i].X>>arr[i].Y;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(DIS(a,b) < DIS(i, j))
a=i, b=j;
cout<<a<<' '<<b<<'\n';
cin>>n;
}
return 0;
}