プロジェクトオイラー問165 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20165
乱数により線分の座標を生成するので何個異なる座標の交点があるか答える問題。

外積とベクトル演算の概念を使って交点がある事を確かめたらあとは交点座標を計算するだけです。

double型で計算すると同じ点が違う点として判断されることがあるので交点座標は分数として保持します。
後は実装ゲームです。

#include<stdio.h> 
#include<iostream>
#include<vector>
#include<set>
#include<math.h>
#include<stdlib.h> 

__int64 MOD=50515093;

struct E{ 
	int x0,y0,x1,y1;
};
struct E2{
	int xu,yu,xd,yd;
	bool operator<(const E2& e2)const{
		
		if(xu!=e2.xu)return xu<e2.xu;
		if(xd!=e2.xd)return xd<e2.xd;
		if(yu!=e2.yu)return yu<e2.yu;
		return yd<e2.yd; 
	}
};
int 
gcd ( int a, int b )
{
 int c;
 while ( a != 0 ) {
    c = a; a = b%a;  b = c;
 }
  return b;
}

__int64 f(__int64 s){
	return (s*s)%MOD;
} 



bool isCross(E e1,E e2){
	int dx0=e2.x0-e1.x0;
	int dy0=e2.y0-e1.y0;
	int dx1=e2.x1-e1.x0;
	int dy1=e2.y1-e1.y0;
	int dy2=e1.y1-e1.y0;
	int dx2=e1.x1-e1.x0;

	int g1=dx2*dy1-dy2*dx1;
	int g2=dx2*dy0-dy2*dx0;
	if(g1<0&&g2>0)return true;
	if(g1>0&&g2<0)return true;
	return false;
} 

 
E2 crossP(E e1,E e2){
	int dx0=e2.x0-e1.x0;
	int dx1=e2.x1-e1.x0;
	int dy0=e2.y0-e1.y0;
	int dy1=e2.y1-e1.y0;
 	int s1=abs(dx0*dy1-dx1*dy0);
	dx0=e2.x0-e1.x1;
	dx1=e2.x1-e1.x1;
	dy0=e2.y0-e1.y1;
	dy1=e2.y1-e1.y1;
	int s2=abs(dx0*dy1-dx1*dy0);
	
	E2 e3;
	e3.xu=(e1.x1-e1.x0)*s1;
	e3.yu=(e1.y1-e1.y0)*s1;
	e3.xd=s1+s2;
	e3.yd=s1+s2;
	int d1=gcd(e3.xu,e3.xd);
	int d2=gcd(e3.yu,e3.yd);
	e3.xu/=d1;
	e3.xd/=d1;
	e3.yu/=d2;
	e3.yd/=d2;
	
	e3.xu=e3.xu+e1.x0*e3.xd;
	e3.yu=e3.yu+e1.y0*e3.yd;
	d1=gcd(e3.xu,e3.xd);
	d2=gcd(e3.yu,e3.yd);
	e3.xu/=d1;
	e3.xd/=d1;
	e3.yu/=d2;
	e3.yd/=d2;
	
	return e3;
}

int main(){
	std::vector<E> vec;
	E e1;
	__int64 s=290797;

	for(int i=1;i<=5000;i++){
		s=f(s);
		e1.x0=s%500;
		s=f(s);
		e1.y0=s%500;
		s=f(s);
		e1.x1=s%500;
		s=f(s);
		e1.y1=s%500;
		vec.push_back(e1);
	}
	std::set<E2> ans;
	for(int i=0;i<vec.size();i++){
		for(int j=i+1;j<vec.size();j++){
			if(isCross(vec[i],vec[j])&&isCross(vec[j],vec[i])){
				ans.insert(crossP(vec[i],vec[j]));
			}
		}
	}
	printf("%d",ans.size());
}