Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2417-d091c2ba
この記事にトラックバックする(FC2ブログユーザー)

Round #208 DIV2 A問題 - Dima and Continuous Line (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 A問題 (500pt)
Problem description

問題概要

$n$ 個の異なる整数 $x_1,x_2,\ldots,x_n$ が与えられる.
$2$ 次元平面の $y \geq 0$ の部分に,$(x_i, 0)$ と $(x_{i+1}, 0)$ を直径とする半円を描く.
半円が($y > 0$ の部分で)交わるかどうかを判定する問題.
$n \leq 1000$
$-10^6 \leq x_k \leq 10^6$

解法

全ての半円の組に対して交わるかどうかを調べる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))

int main(){
  int n;
  int x[1000];

  int i, j, res;
  int x1_min, x1_max, x2_min, x2_max;
  
  scanf("%d", &n);
  rep(i,n) scanf("%d", x+i);

  res = 1;
  REP(i,1,n) REP(j,1,i){
    x1_min = MIN(x[i-1], x[i]);
    x1_max = MAX(x[i-1], x[i]);
    x2_min = MIN(x[j-1], x[j]);
    x2_max = MAX(x[j-1], x[j]);

    if(x1_min < x2_min && x2_min < x1_max && x1_max < x2_max) res = 0;
    if(x2_min < x1_min && x1_min < x2_max && x2_max < x1_max) res = 0;
  }

  if(res) puts("no"); else puts("yes");

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2417-d091c2ba
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。