[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology