[TIOJ] 1105. H.PS3
題目連結:http://tioj.infor.org/problems/1105
如果我沒猜錯的話,這題應該可以用旋轉卡尺做到$O(n log n)$,但是我實在不熟,加上本題範圍$O(n^2)$就可以過了,所以我就直接寫個裸裸的做法了
如果我沒猜錯的話,這題應該可以用旋轉卡尺做到$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;
}
留言
張貼留言