Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #15 B問題 - Laser (この記事を編集する[管理者用])

Source

Codeforces Beta Round #15 B問題
Problem description
Beta Round #15の自分の参加記録

問題概要

n*mのチョコレート板の2点(x1, y1), (x2, y2)にレーザーが当てられている.
2つのレーザーは最初チョコレート板があった範囲の外にでないように,両方共,同じように移動できる.
レーザーでチョコレート板を溶かしきったとき,残ってるチョコレート板の面積を求める問題.

解法

実際に動かしてみると,x座標とy座標に動かせる範囲はそれぞれ
 n - abs(x1-x2)
 m - abs(y1-y2)
で,その分の長方形だけ4隅のうち対角の2つが削られる.
包除原理より,
 もともとの部分 - 2*削られた部分 + 両方で削れる部分
で答えが出せる.

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int x,y,x1,y1,x2,y2;
  long long res, X, Y, a, b;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d%d%d%d",&x,&y,&x1,&y1,&x2,&y2);
    x1 -= x2; y1 -= y2;
    if(x1<0) x1 *= -1; if(y1<0) y1 *= -1;
    X=x; Y=y; a=X-x1; b=Y-y1;

    res = X*Y;
    res -= a*b*2;
    if(X-2*a<0 && y-2*b<0) res += (X-2*a)*(Y-2*b);
    printf("%I64lld\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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