予選模擬 問4
2点間の距離を求める問題。
2006予選模擬は比較的簡単で大概計算数なんか気にしなくても解けるのだが、この問題はそれなりに気をつけないと時間オーバーの危険をはらんでいる。
とりあえず、我がコードではx軸のデータをソートしておいて、現在距離よりもxだけの距離で離れたらそれ以降処理しないことにした。
ソーティングは、クイックソートを自前で実装するのがめんどくさかったのでstdlib.hのqsort()関数を使った。反則臭い。
#include#include int datax[10000],datay[10000]; int compare_function(int *first , int *second){ //比較関数 int tmp; if(*first < *second){ tmp = datay[datax - first]; datay[datax-first] = datay[datax-second]; datay[datax-second] = tmp; return 1; }else{ tmp = datay[datax-first]; datay[datax-first] = datay[datax-second]; datay[datax-second] = tmp; return -1; } return 0; } int main(void){ int n,i,j; int shortest = 0x7fffffff; int tmp; scanf("%d",&n); for(i=0;i *1+*2; if(tmp < shortest) shortest = tmp; if(datax[j+i] > shortest) break; } for(j=-1;j+i >= 0;j--){ tmp = *3+*4; if(tmp shortest) break; } } printf("%d",shortest); return 0; }