DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 B問題 - ステップカット

Source

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選
問題文

問題概要

$2$ 次元平面上に半径 $R$ の円がある.
また,水平な線が等間隔に無限にあり,上から順番に $\ldots,-2,-1,0,1,2,\ldots$ と番号がついている.
$0$ 番の線と $N$ 番の線は円の上端と下端とそれぞれ接している.
$d_i$ を $i$ 番の線と円の交わる部分の長さと定義する.
正整数 $M$ が別途与えられるので,
\[ \sum_{i=1}^{N+M-1} \max(d_i, d_{i-M}) \]を求める問題.
問題原文の図も参照.

解法

各線が円と交わる部分の長さを三平方の定理などで計算して,後は,求めるべき式を定義通り計算すれば良い.
時間計算量は $O(N+M)$ 程度.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

double R;
int N, M;

double get_dist(int i){
  double d;
  if(i <= 0 || i >= N) return 0;
  d = 2 * R * i / N;
  d = fabs(R-d);
  return 2 * sqrt(R*R - d*d);
}

int main(){
  int i;
  double res = 0;

  reader(&R,&N,&M);
  REP(i,1,N+M) res += max(get_dist(i), get_dist(i-M));
  writerLn(res);

  return 0;
}

Current time: 2017年11月19日12時17分49秒
Last modified: 2016年11月06日16時04分44秒 (by laycrs)
Tags: Competitive_Programming AtCoder ddcc2016-qual
トップページに戻る

Logged in as: unknown user (not login)

ログイン: