30日でできる!OS自作入門6日目

　6日目は割り込み処理について学ぶ。

picの初期化

　5日目でGDTとIDTを初期化をしたが、割り込み処理のためにはPICの設定も必要である。PICは一つの割り込み信号しか受け付けられないCPUを補助するもので、8つの割り込み信号をまとめて1つの信号をCPUに送るものである。マザーボードにはマスターPICとスレイブPICがあり、スレイブPICから割り込み信号を送られてもマスターPICが反応しなければCPUに割り込みを通知されない仕組みになっている。下の図のIRQは割り込み信号のことである。
f:id:achax0511:20181220141513j:plain
川合秀実(2006)・『30日でできる!OS自作入門』 p.127 ,株式会社マイナビ

割り込み番号の振り分け

　以下のPICの初期化プログラムでは、制御データICW2で割り込み信号に対して割り込み番号を振り分けている。そのためこの例ではIRQ0、IRQ1から割り込み信号が送られるとそれぞれ割り込み番号20、21に対応する処理をする。

void init_pic(void)
/* PICの初期化 */
{   //それ以外の処理は省略
　io_out8(PIC0_ICW2, 0x20  ); /* IRQ0-7は、INT 20-27で受ける */
　io_out8(PIC1_ICW2, 0x28  ); /* IRQ8-15は、INT 28-2fで受ける */　                            
}

割り込みハンドラ

　キーボードの割り込み信号はIRQ1、マウスのキーボードはIRQ12なので割り込み番号0x21,0x2cに対応する処理（割り込みハンドラ）を作成する。今回はキーボード入力やマウス操作すると文字が表示される割り込みハンドラを作成する。割り込みは実行している処理を中断して行うので、割り込み前のデータを保存して後に処理を再開できるようにする必要がある。そのためアセンブラ言語でプログラムを書く必要がある。
　以下のプログラムが割り込みハンドラになる。大まかに述べるとこのプログラムでは処理前のレジスタの値をスタックに入れ、C言語で書いた文字を表示する関数を呼び出し、スタックをとりだして割り込み前のレジスタの値に戻している。

_asm_inthandler21:
 PUSH ES
 PUSH DS
 PUSHAD
 MOV EAX,ESP
 PUSH EAX
 MOV AX,SS
 MOV DS,AX
 MOV ES,AX
 CALL _inthandler21
 POP EAX
 POPAD
 POP DS
 POP ES
 IRETD

次にIDTに_asm_inthandler21を設定する。その結果キーボードを入力すると割り込み処理が行われて文字が表示されるようになった。しかし、その後マウスも同じ要領で割り込みハンドラーを作成するが割り込み処理がうまく行われなかった。

f:id:achax0511:20181220180549j:plain
キーボードの割り込み処理

30日でできる!OS自作入門5日目

何をやるか

  • 構造体入門（省略）
  • 文字やマウスカーソルの表示
  • マウスカーソルを動かすためのセグメンテーションと割り込みの入門

構造体入門

  • 構造体は複数の変数をまとめて宣言するものであり、構造体を使うメリットは関数にデータを引き渡すときに引数を減らすことなどが考えられる。
  • 以下の構造体BOOTINFOは、OSのインターフェースの描画に関する設定情報（描画システムの横や縦の解像度）をまとめたものである。
struct BOOTINFO {
	char cyls, leds, vmode, reserve;
	short scrnx, scrny;
	char *vram;
};
  • cyls,leds,vmode,reserve,...*vramの情報をOS本の3日目(p.62)で、メモリーのアドレス0x00ff0から順に保存されている。
  • メモリーに保存されているインターフェースの横のサイズの情報を構造体のポインタで参照するために、構造体の中にある先頭の変数のアドレスstruct BOOTINFO *binfo = (struct BOOTINFO *) 0xf00f0;を代入し、(*binfo).scrnxまたはbinfo->scrnxと書く。

文字表示

　4日目に描いたインターフェースに文字を書く。文字は8*16の長方形の集まりで0,1で表現できる、以下の写真は0,1で’A’を表現したものである。
f:id:achax0511:20181026104959p:plain
参照　川合秀実（２００６）.『30日でできる!OS自作入門』 p.101,株式会社マイナビ

  • プログラムではAを0,1で表現したものを配列データとして16進数で保存する。これをフォントデータとよぶ。
 static char font_A[16] = {
  0x00, 0x18, 0x18, 0x18, 0x18, 0x24, 0x24, 0x24,
  0x24, 0x7e, 0x42, 0x42, 0x42, 0xe7, 0x00, 0x00
 };
  • 下記にはインターフェースに文字を表示させるための関数が書かれている。引数vramは4日目で用いたビデオラムのアドレス、xsizeはインターフェースの横のサイズ、xやyは文字を表示させたい位置、cは文字の色、fontにはAを表現した配列データのアドレスのことである。変数pにはインターフェースに文字表示させる場所に対応するビデオラムのアドレスが書かていて、 変数dにはフォントデータの一つの要素が書かれている。
  • フォントデータの1を白色,0を背景色にすることで文字を表示する。
  • if ((d & 0x80) != 0) { p[0] = c; }はフォントデータの一つの要素を2進数で表現した時に左から一番目の桁が1である場合に、それに対応するビデオラムを白色に塗る。他のif文の処理もある桁が1である場合に同様の処理をしている。このような処理を繰り返して文字を表示する。
void putfont8(char *vram, int xsize, int x, int y, char c, char *font)
{
 int i;
 char *p, d /* data */;
 for (i = 0; i < 16; i++) {
  p = vram + (y + i) * xsize + x;
  d = font[i];
  if ((d & 0x80) != 0) { p[0] = c; }
  if ((d & 0x40) != 0) { p[1] = c; }
  if ((d & 0x20) != 0) { p[2] = c; }
  if ((d & 0x10) != 0) { p[3] = c; }
  if ((d & 0x08) != 0) { p[4] = c; }
  if ((d & 0x04) != 0) { p[5] = c; }
  if ((d & 0x02) != 0) { p[6] = c; }
  if ((d & 0x01) != 0) { p[7] = c; }
  }
 return;
}

この関数を用いて文字”A”を表示させた。
f:id:achax0511:20181026155339j:plain


この後A以外のフォント、値、マウスカーソルを表示する。
f:id:achax0511:20181026160144j:plain

セグメンテーション,割り込みの入門

描いたマウスカーソルを動かすためにセグメンテーションや割り込みの話が関わってくる。

セグメンテーション

  • プログラムをメモリーに読み込ませるために、アセンブラ言語ではORG命令で ORG 0x1234という風に番地を指定する必要があった。しかしアプリケーションを複数読み込ませる時に、ORG命令を用いるとメモリーの利用範囲が重なることがありエラーがおきてしまうことがある。これを解消するためにセグメンテーションが必要である。
  • セグメンテーションはメモリーをブロックごとに好きに切り分けて、最初の番地を0として扱える機能である。どのプログラムも ORG 0 と書いても問題がなくなる。
  • セグメンテーションは一つのセグメント（ブロック）を表すために以下の設定情報が必要である。
    • セグメントの大きさ
    • セグメントはどの番地から始まるのか
    • セグメントの管理用属性（書き込み禁止・実行禁止・システム専用）
  • CPUでは3つの設定情報を8バイトであらわされている。複数のセグメントの情報を並べたものをGDTとよぶ。
  • グラフィック色番号（4日目）と同じようにセグメント番号があり、セグメントレジスタを用いてどのセグメントがどのセグメント番号に対応させるかの設定が必要である。

割り込み

  • 外部からの入力が起きたときに臨時で処理を切り替えさせる機能で、マウスカーソルを動かすためには必要である。
  • 割り込みが起きたときに処理を切り替えて後で再開可能できるようにし、設定した処理を行う。
  • IDTはGDTと同様に複数の割り込みの設定情報を並べたものである。

30日でできる!OS自作入門4日目

何をやるか

  • アセンブラみたいにC言語でメモリーに書きこみたい。そこでC言語のポインタを用いてメモリーを書きかえる。
  • VRAMを書き換えると画面の色を変えることができるので、ポインタを用いて書き換える。
  • 色番号の設定してGUIを描く。

画面の表示入門

 VRAMがある0xa0000～0xaffff番地を p=(char *)i;*p=i & 0x0f;と書いて換える。i番地に0x0fをandすると00,01,02,03,04,05,06,07,08,09,0A,0B,0C,0D,0E,0F,00,...という16画素ごとに色番号を繰りかえす。そのため320×200の画面に繰り返された値が代入されて縞々模様が表示される。

void io_hlt(void);

void HariMain(void)
{
 int i;
 char *p;

 for(i=0xa0000; i<=0xaffff; i++){
  p=(char *)i;
  *p=i & 0x0f; 
 }

 for (;;) {
  io_hlt();
 }
}

 実際に出力された縞々模様の画面。見ていると目が痛くなりそう。
f:id:achax0511:20180821213134j:plain


 また p=(char *)i; *p=i & 0x0f;をアセンブラで説明すると、以下のようにECXレジスタにメモリーの番地を代入して、ECX番地に(i & 0x0f)を代入するという説明は大変分かりやすかった。

MOV ECX i 
MOV BYTE[ECX],(i & 0x0f)

色番号の設定

 現在は320×200の8ビットカラーモードで画面を表示しているため、扱える色は乏しくOSのGUIを描くのは難しい。そのため、色番号を設定し直す必要がある。0～15の色番号を黒、明るい赤、明るい黄色などの16色を設定する。 色番号の設定のためにビデオDAコンバーターのパレットにアクセスして書き換える必要がある。色はカラーコードのサイトが参考になる。

  • パレットにアクセスして書き換える手順
    • 割込みがはいらないように割込みフラグを0にする。アセンブラのCLI命令をする。
    • out命令を用いて0x03c8に設定したいパレット番号を書き込む。
    • out命令を用いて0x03c9にR,G,Bの順に値を書き込む。そうすることによってパレット番号の色が変わる。また、RGBを書き込む続けると設定した次の番号の色も書き変わる。
    • 最初にCLI命令したのを元に戻す。アセンブラのSTI命令をする。

 割込みフラグは32ビットレジスタのEFLAGSの9ビット目にあるので状態をチェックするのは困難である。実装ではCLI命令する前にEFLAGSの値を保存して、色の設定番号を書き換え後にEFLAGSレジスタに保存した値を代入する方法をとる。多分CLI命令する前の状態で割込みフラグが0の場合を考慮して、STI命令ではなくこの方法をとるのだろう。
 C言語に書くと以下になるが、なぜio_out8(0x03c9, rgb[0] / 4); でrgbを4で割る理由がわからない。

void init_palette(void)
{
  static unsigned char table_rgb[16 * 3] = {
    0x00, 0x00, 0x00,  /*  0:黒 */
    0xff, 0x00, 0x00,  /*  1:明るい赤 */
    0x00, 0xff, 0x00,  /*  2:明るい緑 */
    0xff, 0xff, 0x00,  /*  3:明るい黄色 */
    0x00, 0x00, 0xff,  /*  4:明るい青 */
    0xff, 0x00, 0xff,  /*  5:明るい紫 */
    0x00, 0xff, 0xff,  /*  6:明るい水色 */
    0xff, 0xff, 0xff,  /*  7:白 */
    0xc6, 0xc6, 0xc6,  /*  8:明るい灰色 */
    0x84, 0x00, 0x00,  /*  9:暗い赤 */
    0x00, 0x84, 0x00,  /* 10:暗い緑 */
    0x84, 0x84, 0x00,  /* 11:暗い黄色 */
    0x00, 0x00, 0x84,  /* 12:暗い青 */
    0x84, 0x00, 0x84,  /* 13:暗い紫 */
    0x00, 0x84, 0x84,  /* 14:暗い水色 */
    0x84, 0x84, 0x84  /* 15:暗い灰色 */
  };
  set_palette(0, 15, table_rgb);
  return;
  /* static char 命令は、データにしか使えないけどDB命令相当 */
}

void set_palette(int start, int end, unsigned char *rgb)
{
  int i, eflags;
  eflags = io_load_eflags();  /* 割り込み許可フラグの値を記録する */
  io_cli();           /* 許可フラグを0にして割り込み禁止にする */
  io_out8(0x03c8, start);
  for (i = start; i <= end; i++) {
    io_out8(0x03c9, rgb[0] / 4); //4を割る理由はなんなんだろうか
    io_out8(0x03c9, rgb[1] / 4);
    io_out8(0x03c9, rgb[2] / 4);
    rgb += 3;
  }
  io_store_eflags(eflags);  /* 割り込み許可フラグを元に戻す */
  return;
}

 関数io_cli(); io_out8(); io_store_eflags(eflags)は、Cでは扱えない命令があるためアセンブラ言語で定義する必要がある。以下がコードである。

_io_cli:	; void io_cli(void);
		CLI
		RET

_io_out8:	; void io_out8(int port, int data);
		MOV		EDX,[ESP+4]		; port
		MOV		AL,[ESP+8]		; data
		OUT		DX,AL
		RET
_io_load_eflags:	; int io_load_eflags(void);
		PUSHFD		; PUSH EFLAGS という意味
		POP		EAX
		RET

_io_store_eflags:	; void io_store_eflags(int eflags);
		MOV		EAX,[ESP+4]
		PUSH	EAX
		POPFD		; POP EFLAGS という意味
		RET

 コードから以下のことが分かった。

  • io_out8関数の引数の値がメモリーのESP番地以降に格納されている。引数の値はint型の32ビットなので一つの引数に4番地使われる。恐らくMOV ESX,[ESP+4]されるとESXは上位ビットから[ESP+7],[ESP+6],[ESP+5],[ESP+4]と値が代入されるのだろう。
  • io_load_eflagsはMOV EAX EFLAGSが仕様でできないので、EFLAGSをスタックにプッシュしてポップした値をEAXに格納する受け渡しになる。return文であるRET命令で関数が終了した時関数のEAXは返り値になる。
  • io_store_eflagsはMOV EFLAGS EAXができないのでio_load_eflagsと同様にスタックを介してデータの受け渡しを行う。

 0~15の設定番号を変えた場合の縞々模様の画面
f:id:achax0511:20180822152151j:plain


 4日目では最終的にこういうGUIを描いた。
f:id:achax0511:20180822154729j:plain

感想

色番号を設定し直すところで割込みやEFLAGSレジスタなどの新しい話が多くて、少しややこしかった。
まとめるのに時間がかかった。一日一日をもうちょっとコンパクトにまとめた方がいいように思える。

30日でできる!OS自作入門3日目

何をやるか

  • ブートセクターにフロッピーをロードするIPLを作成する。
  • アセンブラ言語だけではなくC言語でプログラムを書くための準備をする。

新しく出たアセンブラ言語の命令など

  • JC キャリーフラグが1なら指定先にジャンプする。キャリーフラグは読み込みエラーが起こったときに1が出力される。
  • JNC キャリーフラグが0なら指定先にジャンプする。つまり読み込みエラーがなければ指定先にジャンプするということである。
  • JBE CMP命令で比較して値が小さいかもしくは等しければジャンプする。
  • EQU 命令じゃないだけどC言語の#defineみたいなもの。CYLS EQU 10はCYLSは10ですよという意味である。

フロッピーディスクについて

  • フロッピーは0～79の円形のシリンダーで構成されている。シリンダーはヘッダーを切り替えることによって表と裏の読みこみできる
  • シリンダーは1～18のセクター(512KB)で構成されている。シリンダーとセクターは0-indexで統一しない理由はなんでなのか少し気になるな。
  • シリンダーの読み込み方が一つのシリンダーの表と裏を読んだら、次のシリンダーを読むようになっている。

プログラムを読んで

  • MOV [678] 123みたいなメモリーに値を代入する命令はないが、恐らくretryの処理のところのINT 0x13命令で読み込んだ値がメモリーに格納されている。メモリーに読み込んだ値を格納する番地（バッファアドレス）の指定方法はESレジスタやBXレジスタに値を導入することによって計算される。
  • 多分、INT命令の所でmov [ES:BX] 読み込んだ値　が命令されているのだろう。　ES:BXはES×16+BXで計算され、ESやBXはそれぞれ16ビットのため最大表現でできる数は0xffffであるため、ES:BXで最大表現できる数は1,113,095バイト(1MB)である。
entry:
    MOV    AX,0      ; レジスタ初期化
    MOV    SS,AX
    MOV    SP,0x7c00
    MOV    DS,AX

; ディスクを読む

    MOV    AX,0x0820
    MOV    ES,AX
    MOV    CH,0      ; シリンダ0
    MOV    DH,0      ; ヘッド0
    MOV    CL,2      ; セクタ2
readloop:
    MOV    SI,0      ; 失敗回数を数えるレジスタ
retry:
    MOV    AH,0x02      ; AH=0x02 : ディスク読み込み
    MOV    AL,1      ; 1セクタ
    MOV    BX,0
    MOV    DL,0x00      ; Aドライブ
    INT    0x13      ; ディスクBIOS呼び出し
    JNC    next      ; エラーがおきなければnextへ
    ADD    SI,1      ; SIに1を足す
    CMP    SI,5      ; SIと5を比較
    JAE    error      ; SI >= 5 だったらerrorへ
    MOV    AH,0x00
    MOV    DL,0x00      ; Aドライブ
    INT    0x13      ; ドライブのリセット
    JMP    retry
next:
    MOV    AX,ES      ; アドレスを0x200進める
    ADD    AX,0x0020
    MOV    ES,AX      ; ADD ES,0x020 という命令がないのでこうしている
    ADD    CL,1      ; CLに1を足す
    CMP    CL,18      ; CLと18を比較
    JBE    readloop    ; CL <= 18 だったらreadloopへ
    MOV    CL,1
    ADD    DH,1
    CMP    DH,2
    JB    readloop    ; DH < 2 だったらreadloopへ
    MOV    DH,0
    ADD    CH,1
    CMP    CH,CYLS
    JB    readloop    ; CH < CYLS だったらreadloopへ

C言語導入

C言語のプログラムでHLT命令を扱えるようにするために以下のことをする。（かなりはしょっている気がするが。。。）

  • アセンブラのプログラムで32ビットの機械語を扱うモードを設定し、HLTを扱う関数をGLOBALで定義する。そしてオブジェクトファイルに変換する
  • C言語のプログラムは、アセンブラ言語で定義したHLTを扱う関数を用いる。そしてオブジェクトファイルに変換する。
  • 最後に生成された二つのオブジェクトファイルをくっつける。

感想

C言語を導入するための、アセンブラの方での設定や変換についてはあまり理解できていないと思う。
書くのが億劫で3日目をまとめるのに少し時間がかかった。プログラムを読んだり実行するだけしかしていないので、せめてまとめることは続けたい。4日目からはC言語を扱うということなので少し楽しみだ。

30日でできる!OS自作入門2日目

何をやるか

一日目のアセンブラプログラムの理解の続きとmakeファイル入門。
Hello worldを出力するOSプログラムを改良して何をやっているのかを理解する、アセンブラプログラムをイメージファイルに変換するバッチファイルやイメージファイルを用いてqemuでエミュレートするバッチファイルなどをまとめてMakefileに書く。

新しく出たアセンブラの命令

新しく出てきた命令などについて書く。

  • ORG命令 プログラムがメモリーのどこから格納されるかを設定するために使う。
  • JMP命令 指定されたアドレスに飛ぶ。
  • MOV命令 代入を表す。CPUの記憶装置やメモリーにアドレスや値を代入するために使う。
  • INT命令 ソフトウェア命令割込み。
  • CMP命令 比較を行う命令。
  • JE命令　比較の結果が等しければ指定したアドレスにジャンプする。
  • ラベル 変数名;と書くとラベルの宣言がかける。命令のアドレスを分かるために宣言する。

プログラムを読んで

  • 最初のORG命令でPCのメモリーにプログラムを読み込ませる番地を0x7c00と書く理由は決まり事で、0x0000とかはBIOSが使うことがあるのでだめらしい。
  • ディスプレイに"Hello world"を出力するために、メモリーに格納されている文字をCPUのALレジスタに一文字ずつ代入していることが、putloop:のところのMOV AL,[SI]　ADD SI 1 でわかる。SIレジスタは文字列の書き込み命令が書かれているmsgの番地が代入されている。ORG命令のところでADD msg 0x7c00されてmsgのメモリーからの絶対番地は既に計算されているのかな？
  • putloopのところでALレジスタに代入された文字を出力するために、MOV AH,0x0e　MOV　BX,15　INT 0x10とBIOSのビデオ関係の制御をしている。INT命令について後々わかればいいな。
; hello-os
; TAB=4

    ORG    0x7c00      ; このプログラムがどこに読み込まれるのか

; 以下は標準的なFAT12フォーマットフロッピーディスクのための記述

    JMP    entry
    DB    0x90
; プログラム本体

entry:
    MOV    AX,0      ; レジスタ初期化
    MOV    SS,AX
    MOV    SP,0x7c00
    MOV    DS,AX
    MOV    ES,AX

    MOV    SI,msg
putloop:
    MOV    AL,[SI]
    ADD    SI,1      ; SIに1を足す
    CMP    AL,0
    JE    fin
    MOV    AH,0x0e      ; 一文字表示ファンクション
    MOV    BX,15      ; カラーコード
    INT    0x10      ; ビデオBIOS呼び出し
    JMP    putloop
fin:
    HLT            ; 何かあるまでCPUを停止させる
    JMP    fin        ; 無限ループ

msg:
    DB    0x0a, 0x0a    ; 改行を2つ
    DB    "hello, world"
    DB    0x0a      ; 改行
    DB    0

    RESB  0x7dfe-$    ; 0x7dfeまでを0x00で埋める命令

    DB    0x55, 0xaa

Makefileを書いて出力されたエラー

  • ../z_tools/・・・の命令の所で先頭にタブ文字を挿入していないと"Makefile:2: *** missing separator. Stop."とエラーがでた
ipl.bin :ipl.nas Makefile
	../z_tools/nask.exe ipl.nas ipl.bin ipl.lst
  • cygwinを導入していると最後のMakafileのcleanが実行できなくて"process_begin: CreateProcess((null), del ipl.bin, ...) failed.make (e=2): 指定されたファイルが見つかりません。..\z_tools\make.exe: [clean] Error 2 (ignored) del ipl.lst"とエラーが出る。 faq/makeを読むと以下のように書き換えたらよいらしい。
clean :
	cmd.exe /C del ipl.bin
	cmd.exe /C del ipl.lst

感想

何とか二日目を終わらすことができた。30日OSは色々と参考になるブログがあって、困ったことはググればなんとかなるので助かる。この気力が続けばいいな。

30日でできる!OS自作入門 1日目

30日でできる! OS自作入門

30日でできる! OS自作入門

OS自作入門というタイトルに引かれて読み始めました。三日坊主の僕には続くか分からないですがやってみようかと思います。だいぶ前の本でフロッピーからOSを起動させるのですが、qemuというエミュレータを用いて起動させる事もしているので今のwindows機でも学習していけるのじゃないかと思います。

環境

windows 10 home 64ビットオペレーティングシステム

一日目のやること

フロッピーディスクからOSを起動させるプログラムをバイナリーエディタ（BZ）や筆者作アセンブラ言語（nask)で書く。この起動させるプログラムはコンピュータがブートセクターを読んだ時に出力される部分だけである。フロッピーは一つのセクター（512バイト）ごとに読まれ、ブートセクターとはフロッピーが最初に読まれるセクターで、最後の部分に55AAと書く決まりがある。本来ブートセクターには容量のためにOSを読み込ませるプログラムを格納できないので、IPLというOS本体を読み込むプログラムが書かれている。一日目はosを起動させたときに"hello world"を出力するプログラムをブートセクターに作成する。


機械語について

フロッピーディスクサイズ分(1440KB)機械語を書く勇気がなかったので筆者のサンプルを利用した。
下の写真はフロッピーのフォーマットや起動したときに出力されるプログラムが書かれていて、表示されている機械語は16進数である。

f:id:achax0511:20180808173534p:plain


下の写真55AAと書かれている1F0（１６進数）行目がブートセクターの終わりである。
f:id:achax0511:20180808175159p:plain


下の写真はqemuで先ほど書いた機械語をエミュレートした結果である。"hello,world"と出力できた。2004年って14年前か・・・
f:id:achax0511:20180808182659p:plain


アセンブラについて

サンプルで出てくる命令のメモについて書く。

  • DB(data byte)命令は機械語の命令を一バイトずつ書くのや文字列を書くことができる。
  • RESB(reserve byte)命令は領域を予約する命令で0x00を連続して沢山書く場合に省略して書くのができる。
  • DW(data word)命令はDB命令の仲間でwordは2バイトを表している。何を2バイト書くのか分からないが
  • DD(data double-word)命令はDB命令の仲間でdouble-wordは4バイトを表している。


DB命令のところをいじってhello worldを変えてqemuでエミュレートした。
f:id:achax0511:20180808185815j:plain

感想

機械語で書くのは大変だからアセンブラで書くと楽だよということが分かった。よくわからない状態だがなんとか一日目が終わった、続けたいな。

Codeforces Round 500 div2 C.Photo of The Sky

C. Photo of The Sky

問題
n個の星のx,y座標の値が適当にa_{1},a_{2},...,a_{2n}と書かれている。
これらのa_i (1 \leq i \leq 2n)からn個の星の座標(x_1,y_1),(x_2,y_2) ,...(x_n,y_n) (x_1 \leq x_2 \leq ...\leq x_n , y_1 \leq y_2 \leq... \leq y_n ) を作成する。このときn個の星がうつる長方形の考えうる面積(x_n-x_1) \times (y_n-y_1) の最小値を求めよ。
解法

  • まずa_i(1 \leq i \leq 2n)を昇順にソートする。
  • a_iをn個のx座標値の集合Xとn個のy座標の集合Yに分割した場合を考えると、Xに最小値a_1,最大値a_{2_{n}}が入っている場合とXに最小値a_1,Yに最大値a_{2_{n}}が入っている場合が考えられる。そのためそれぞれの場合の面積の最小値を求める必要がある。
    • Xに最小値a_1,最大値a_{2_{n}}が入っている場合はi(2 \leq i \leq 2n-1)に関して a_{i+n-1}-a_iが最小なa_iがYの最小値、a_{i +n-1}がYの最大値として面積を計算する。
    • Xに最小値a_1,Yに最大値a_{2_{n}}が入っている場合は,XやYそれぞれの最大値と最小値の差を小さくするために、Xの最大値をa_n,Yの最小値をa_{n+1}として面積を計算する。

ソースコード

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<iomanip>
using namespace std;

int main(void){
 int x1,x2;
 int y1,y2;
 int a,n;
 long long int ans=9000000000000000000;
 int ok=0;
 long long int sum=0;
 vector<int> A;
 cin>>n;
 for(int i=0; i<2*n; i++){
  cin>>a;
  A.push_back(a);
 }
 sort(A.begin(),A.end());

 x1=A[0];//xに最小値
 x2=A[2*n-1];//xに最大値
 for(int i=1;(i+n-1)<2*n-1; i++){
  y1=A[i]; 
  y2=A[i+n-1]; 
  sum=(long long int)abs(x2-x1)*abs(y1-y2);
  if(sum<ans)ans=sum;
 }

 x1=A[0];//Xに最小値
 y2=A[2*n-1];//Yに最大値

 x2=A[n-1];
 y1=A[n];
 sum=(long long int)abs(x1-x2)*abs(y1-y2);
 if(sum<ans)ans=sum;

 std::cout<<ans<<std::endl;
 return 0;
}

解説