AOJ0010 - Circumscribed Circle of a Triangle

計算するだけなんですけど,色々と面倒臭かった.

AOJ0010

参考:kanetaiの二次記憶装置

各点から円の中心までの距離(つまり半径)が全て等しいことを考える.

各点を { A(x_1, y_1)} { B(x_2, y_2)} { C(x_3, y_3)} と置く.
また中心の座標を{ P(x_p, y_p)} と置く.

半径が等しいということは

{ | \vec{PA}| = | \vec{PB}| = | \vec{PC}|}

これらを連立方程式として解けば{ x_p}{ y_p}が求まる.

連立方程式は以下のようになる.

{
\begin{cases}
\; 2(x_1 - x_2)x_p + 2(y_1 - y_2)y_p = x_1^2 + y_1^2 - x_2^2 - y_2^2 \\
\; 2(x_1 - x_3)x_p + 2(y_1 - y_3)y_p = x_1^2 + y_1^2 - x_3^2 - y_3^2
\end{cases}}

行列を用いて,

\begin{pmatrix} 2(x_1 - x_2) & 2(y_1 - y_2) \\ 2(x_1 - x_3) & 2(y_1 - y_3) \\ \end{pmatrix}

逆行列

\begin{pmatrix} x_1^2 + y_1^2 - x_2^2 - y_2^2 \\ x_1^2 + y_1^2 - x_3^2 - y_3^2 \\ \end{pmatrix}

の積を求めればよい.

また,半径の長さは先程の { | \vec{PA}| = | \vec{PB}| = | \vec{PC}|} どれか一つに代入して求める.

コード

#define sq(x) ((x) * (x))

signed main()
{
  int n;
  scanf("%d", &n);

  while (n--){
    double x1, y1, x2, y2, x3, y3;
    scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3);

    double a = 2 * (x1 - x2), b = 2 * (y1 - y2),
           c = 2 * (x1 - x3), d = 2 * (y1 - y3);
    double e = sq(x1) + sq(y1) - sq(x2) - sq(y2),
           f = sq(x1) + sq(y1) - sq(x3) - sq(y3);

    double x = (1 / (a * d - b * c)) * (d * e - b * f),
           y = (1 / (a * d - b * c)) * (-c * e + a * f);

    double r = sqrt(sq(x - x1) + sq(y - y1));
    printf("%.3f %.3f %.3f\n", x, y, r);
  }

  return 0;
}

工藤忍は最高や!!ということをプレゼンした(LT)

こんにちは.kurokojiです. 今回は2016/5/12(Thur)に発表したLTについてです.

(記事にするの1ヶ月遅れたおじさんの顔)

スライド

LT

今まで一番楽しかった.自分が好きなことだからやっぱり楽しいよね.


以下忍の話

忍担当です

最初に手に入れたRの帽子を被った垢抜けないような格好(それはそれであり(画像は「工藤忍」でggったら分かると思う))から R+で前髪を出し,左足を後ろに上げ,とてもキュートな姿に瞬間にぼくは

尊い 優勝 天才 神

と感じました.

モバマス始めた

デレステからシンデレラガールズを知りましたが,Pになるにはやはりモバマスもやるべきではと思い,始めました.(結構前に) 最近やっと慣れてきた感じです.

第5回シンデレラガール総選挙

残念ながらランクインならずでしたね. 全て忍に投票したのですがモバマスは未だに無課金故に,ぼく個人の数が圧倒的に少なすぎました.反省点です.

しかし,忍が所属するグループ『フリルドスクエア』のメンバー「喜多見柚」が大健闘の全体11位,Pa4位でした.すごい.

この影響で忍のみならずフリルドスクエアメンバーの人気も上がってほしいです.

ということでね

これからも頑張りたいと思います.

AOJ0594 - Super Metropolis

問題見たとき幅優先かなと思い,実装したら間違ってて悲しくなったのでブログに残しておきます.

AOJ0594

右下と左上方向に移動するときは斜めの道が使えないので,マンハッタン距離の分だけ移動. それ以外は差の絶対値が大きいほうを取る.

コード

// テンプレは省略

signed main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int W, H, N;
  int px, py;
  cin >> W >> H >> N;
  
  // スタート地点
  cin >> px >> py;
  int ans = 0;
  REP(i, N - 1){
    // ゴール地点
    int nx, ny;
    cin >> nx >> ny;
    // 右下と左上に行くときはマンハッタン距離の分だけ移動する
    if (px > nx && py < ny || px < nx && py > ny){
      ans += abs(px - nx) + abs(py - ny);
    } else {
      // 斜めの道を使うときはX,Yそれぞれの差の絶対値が大きいほうを取る
      ans += max(abs(px - nx), abs(py - ny));
    }
    // スタート地点の更新
    px = nx; py = ny;
  }
  print(ans);
  
  return (0);
}

Ubuntu14.04 LTSでIntuos CTL-490を動かす

こんにちは.kurokojiです.最近はUbuntu16.04LTSがリリースされましたね.

さて今回は『Ubuntu14.04でIntuos CTL-490を動かす』という記事ですが,まず

Intuosってなんやねん

ってことですよね.

Intuosとは

Intuos」は、このたび従来のIntuos5からモデルチェンジ したIntuos Proと、従来のペンタブレット製品である BambooがモデルチェンジしたIntuosからなるペンタブレット・ブランドです。プロフェッショナルの使用を前提とした Intuos Proと...
Intuos | Our People | Wacom


ペンタブです

姉になぜか買ってもらいました.ありがとうございます.

Ubuntuで動かす

ここからが本題なのですが,ぼくの持っているIntuos CTL-490Ubuntuで刺しただけでは動きませんし,公式がUbuntu用のドライバを配布してません.なんかwacom製のは動くって聞いたけど動きませんでした.残念.

そこで諦めるわけにはいかないので,なんとか動く方法を探しました.
Ubuntu intuos ctl 490」でググるこんなのがありました.

try to install this driver...
download from the link: http://sourceforge.net/projects/linuxwacom/files/xf86-input-wacom/input-wacom/input-wacom-0.30.0.tar.bz2
unzip the file
open the terminal and go to the directory
run:
・ 4.1 - ./configure
・ 4.2 - make
・ 4.3 - sudo make install
plug the wacom tablet and be happy!
it worked for me!
Ubuntu 14.04. 2 does not recognize my Wacom Intuos tablet draw (ctl-490b)

簡単に訳せば,

  • ここからドライバをDLしてね
  • 解凍してね
  • ターミナル開いてね
  • 解凍したディレクトリに移動して
    • ./configure
    • make
    • sudo make install すると

ペンタブ使えて幸せになれるよ!!!!

ということです. その通りにやって再起動すると動きました.やったぜ.
英語に屈せずにちゃんと読んでよかったです.

GIMPとかも筆圧検知して動いてくれます.筆圧ONにする方法はググってください.
以上です.

カンマ区切りでwhile,for,if文などの条件式を書く時の注意点

自分はこれで苦労したことがあったので備忘録としても書いておくことにする

CやC++ではif(0 < n)などのように括弧内に条件式を書く.
これはwhile(0 < n) for(;i < n;) のようにwhile for文にも同じように書ける.

AOJ等でこんな問題が出る.
カードゲーム | Aizu Online Judge

標準入出力を行うプログラムを作成して下さい。
上記の形式で複数のデータセットが与えられます。nが0のとき入力が終了します。

nの入力の部分だけなら

while (1){
  scanf("%d", &n);
  if (n == 0){
    break;
  }
}

このように書けるだろう.しかしこういう風にも書ける.

while (scanf("%d", &n), n != 0)

後者のほうがコンパクトで見やすい.
因みに,while (scanf("%d", &n), n)と書いても同じような結果になる.
これは,(カンマ)以降に書かれているものを条件式としている.

ただし,このような書き方で注意すべき点がある.
ビデオテープ | Aizu Online Judge

複数のデータセットが与えられます。各データセットは以下のとおりです。
時(整数)分(整数)秒(整数)
入力は、3つの -1 で終わります。

分かった!!さっきの書き方でやると...

while (scanf("%d%d%d", &h, &m, &s), h != -1, m != -1, s != -1)

これでは間違い.この書き方ではs != -1しか条件式として扱ってくれない.
この問題では3つの終了する条件があるので,論理演算子 を使う必要がある.

h-1のときとm-1のときとs-1のときだから...

while (scanf("%d%d%d", &h, &m, &s), h != -1 && m != -1 && s != -1)

一見正解に見えるが,実はこれも間違い.ここで改めて論理演算子の意味を思い出してほしい.
以下はa && b,a || bのときを表している.

&&
a b 真偽
0 0 0(偽)
1 0 0(偽)
0 1 0(偽)
1 1 1(真)
||
a b 真偽
0 0 0(偽)
1 0 1(真)
0 1 1(真)
1 1 1(真)

例えば先程のコードで-1 2 2と入力したとする.
条件は 3つの-1で終わる ことだ.しかしこれではwhileを抜けてしまい終了してしまう.
詳しく見ていこう.

h には-1m には2s には2 が入る.
まずh != -1これは0(偽)になる.m != -1 これは1(真).s != -1も1(真)だ.
論理演算子&&なので表に合わせてみると0 && 1 && 1になり最終的に0になる.
0ということはwhile文を抜けることになる.3つとも-1ではない のにだ.

なので正解は

while (scanf("%d%d%d", &h, &m, &s), h != -1 || m != -1 || s != -1)

これなら0 || 1 || 11になり条件に合わずに抜けることが無くなる.
考えてみれば当然だが,,(カンマ)で区切らない方法で書くと

while (1){
  scanf("%d%d%d", &h, &m, &s);
  if (h != -1 && m != -1 && s != -1){ // ||じゃなくて&&
    break;
  }
}

となり&&で書くのでカンマ区切りと逆になってしまう.
僕のようなプログラミング初心者が躓いてしまい,AOJでWAを出される羽目になってしまうので注意していただきたい. (因みにこの問題ではチェックが甘いのでh != -1だけでも通る)

何か間違っている点があればコメント等で教えていただけると幸いです.

AOJ0611 - Silk Road (DP)

AOJ0611のSilk RoadをDPの練習として解いてみました.
また,この問題を解くにあたって以下のサイトを参考にしました.

コード

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define MAX_D (1000)
#define MAX_C (1000)
 
int N, M;
int D[MAX_D], C[MAX_C];
// -1ならまだ調べていない
int dp[MAX_D + 1][MAX_C + 1];
 
int rec_dp(int now, int day);
 
int main()
{
  scanf("%d%d", &N, &M);
  memset(dp, -1, sizeof(dp)); // -1でメモ化テーブルを初期化
 
  for (int i = 0; i < N; i++) scanf("%d", &D[i]);
  for (int i = 0; i < M; i++) scanf("%d", &C[i]);
 
  printf("%d\n", rec_dp(0, 0));
 
  return (0);
}

// nowは現在地,dayは何日目かを表す
int rec_dp(int now, int day)
{
  if (dp[now][day] != -1){ // 一度調べていたら再利用
    return (dp[now][day]);
  }
   
  int res;
  if (now == N){ // 目的地に到着
    res = 0;
  }
  else if (N - now == M - day){ // 目的地に到着するためには進むしかない場合
    res = rec_dp(now + 1, day + 1) + (D[now] * C[day]);
  }
  else { // 進むか待機するか決められる場合
    res = min(rec_dp(now, day + 1), rec_dp(now + 1, day + 1) + (D[now] * C[day]));
  }
 
  dp[now][day] = res; // 結果を保存
 
  return (dp[now][day]);
}

提出したやつ

今回はメモ化再帰のDPで解きました.
またmemsetを初めて使ってみました.(31行目がdp[now][day] != 0でもいけそう)
単純な再帰に手を加えると計算効率がだいぶ上がるので,マスター出来るようにしたい.
また,漸化式を用いたDPも出来るようになりたい.(forだけで書けるので見た目もタイプ量も減りそう)
もっとこここうした方がいいよ,などあればコメント等に書いて頂ければ幸いです.

(この記事はictechの「Markdown超入門」を受け,Markdownで書かれています)