Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Longest Increasing Subsequence"
https://onlinejudge.u-aizu.ac.jp/problems/CGL_5_A
・最近点対
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #CGL_5_A : Longest Increasing Subsequence
/* Aizu Online Judge in C++ #CGL_5_A : Longest Increasing Subsequence https://onlinejudge.u-aizu.ac.jp/problems/CGL_5_A 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; double x[100001],y[100001]; pair<double,double> p[100001]; int main(void){ int n; cin>>n; for(int i=0;i<n;i++){ double X,Y; cin>>X>>Y; x[i]=cos(1)*X-sin(1)*Y; y[i]=sin(1)*X+cos(1)*Y; p[i]=make_pair(x[i],y[i]); } sort(p,p+n); double ans=99999999; for(int i=0;i<n;i++){ for(int j=i-1;j>=0;j--){ if(p[i].first-p[j].first>ans){ break; } ans=min(ans,sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second))); } } printf("%.12f\n",ans); return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/