「プロジェクトオイラー問い101～110」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問い101～110 - (2013/01/04 (金) 10:00:15) の編集履歴(バックアップ)

---

問い102　内部に原点を含む三角形はファイル内にいくつあるでしょう?

3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる.
以下の2つの三角形を考える.
A(-340,495), B(-153,-910), C(835,-947)
X(-175,41), Y(-421,-714), Z(574,-645)
三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる.
27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点を含む三角形の数を答えよ.
注: ファイル中の最初の二つは三角形ABC, XYZである.

解法
3つの点のうち2点を選ぶ組み合わせ3通りで外積の正負が3通りとも同じならその三角形は原点を内部に含みます。

#include<stdio.h>
int main(){
	int xs[3],ys[3];
	char c1,c2;
	int ans=0;
	for(int i=0;i<1000;i++){
		for(int i=0;i<3;i++)scanf("%d%c%d%c",&xs[i],&c1,&ys[i],&c2);
		int p=0,m=0;
		for(int i=0;i<3;i++)xs[i]*ys[(i+1)%3]-ys[i]*xs[(i+1)%3]>=0?p++:m++;
		if(p==3||m==3)ans++;
 	}
	printf("%d",ans);
}

Problem 104 「先頭9桁と末尾9桁が1から9までの数字をすべて含むフィボナッチ数を求めよ」 †

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20104

解法
この問題は多分上位十数ケタと下位9ケタまでを保存しておいて、別々に計算すれば良いだろうなと思いつつ、一応真面目に全桁計算でチャレンジしてみたらいつまでたっても計算が終わらなかったorz
しょうがないので検索かけてカンニングしてみたら大体同じ考え方で解けるみたい。
まじめにやるとあの高速なＬｉｓｐの処理系で時間がかかるとは恐るべき問題。
繰上りで伝播していく時、桁の増加スピードの方が繰上りの伝播スピードより大きくなる桁数が3桁か4桁あたりにあるんだろうな。
一つ勉強になった。

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
__int64 maskDown=1,maskUp=1;
int check(__int64 num){
	char str[11];
	while(num>=maskDown)num/=10;
	sprintf(str,"%d",num);
	
	int count[10]={1,0,0,0,0,0,0,0,0,0};
	for(int i=0;i<9;i++){
		count[str[i]-'0']++;
		if(count[str[i]-'0']>1)return false;
	}
	return true;
}

int main(){
 	__int64 upF1=1,upF2=1,downF1=1,downF2=1,upF3,downF3;
	for(int i=0;i<9;i++)maskDown*=10;
	for(int i=0;i<17;i++)maskUp*=10;
	int ans=2;
	printf("");
	
	while(check(upF2)==false||check(downF2)==false){
		upF3=upF1+upF2;
		upF1=upF2;
		upF2=upF3;
		downF3=downF1+downF2;
		downF1=downF2;
		downF2=downF3;
		while(maskUp<upF2&&maskUp<upF1){
			upF2/=10;
			upF1/=10;
		}
		downF2%=maskDown;
		ans++;
	}
	std::cout<<upF2;
	printf(" %d",ans);
}