4.6 問題7

この本たまに,数学の未解決問題をしれっと問題に入れてるんだけどそんなのアリなの?w


xが[0,1)の範囲で交わらない直線のセットが与えられる.
与えられる直線はy切片が小さい順に与えられる.
与えられる座標(x,y)を挟む二本の直線の座標を求める.


幾何の問題と思ったら負け ;p
回答そのものより,入力データを作るのがうっとおしい気がする.

#include <iostream>
#include <cstdlib>
using namespace std;

int search(double * as, double * bs, int N, double x, double y, int i ){

	double cy = as[i]  *x+bs[i];
	double ny = as[i+1]*x+bs[i+1];
	if( y < cy ){
		return search(as,bs,N,x,y,i/2);
	}else if( ny < y ){
		return search(as,bs,N,x,y,i+(N-i+1)/2);
	}else{
		return i;
	}
}

int main(){
	// 入力作る
	int N = 100;
	double * as = new double[N];
	double * bs = new double[N];

	for(int i=0; i<N; i++){
		double a = i*0.1;
		double b = i*0.1;

		as[i] = a;
		bs[i] = b;
		cout << "(" << a << "," << b << ")" << endl;
	}

	double x = 0.82;
	double y = 2.24;
	int res = search( as, bs, N, x, y, N/2 );
	cout <<"y="<<as[res]  <<"*x+"<<bs[res]  <<""
	     <<" < "
	     <<"("<< x       <<","<< y       <<")"
	     <<" < "
	     <<"y="<<as[res+1]<<"*x+"<<bs[res+1]<<""
	     << endl;
	delete[] as;
	delete[] bs;
	return (0);
}