関数(追記:❌)
typedef complex<double> C;
double cross(C a, C b){
return a.real() * b.imag() - a.imag() * b.real();
}
bool is_intersect(C p0, C p1, C q0, C q1){
auto v0 = p1 - p0;
auto v1 = q0 - p0;
auto v2 = q1 - p0;
if(cross(v0, v1) * cross(v0, v2) >= 0){
return false;
}
v0 = q1 - q0;
v1 = p0 - q0;
v2 = p1 - q0;
if(cross(v0, v1) * cross(v0, v2) >= 0){
return false;
}
return true;
}
使い方
C p0(0, A);
C p1(X, B);
C q0(Sx, Sy);
C q1(Tx, Ty);
bool f = is_intersect(p0, p1, q0, q1);
if(f){
p_yes();
}else{
p_no();
}
追記:Ver 2(追記:AOJで通らないので❌)
typedef complex<double> C;
double cross(C a, C b){
return a.real() * b.imag() - a.imag() * b.real();
}
double inner_product(C a, C b){
return a.real() * b.real() + a.imag() * b.imag();
}
bool in_between(C a, C b, C c){
auto v1 = b-a;
auto v2 = c-a;
if(inner_product(v1, v2)<=0){
return true;
}else{
return false;
}
}
bool is_intersect(C p0, C p1, C q0, C q1){
if(
in_between(p0, q0, q1) ||
in_between(p1, q0, q1) ||
in_between(q0, p0, p1) ||
in_between(q1, p0, p1)
){
return true;
}
auto v0 = p1 - p0;
auto v1 = q0 - p0;
auto v2 = q1 - p0;
if(cross(v0, v1) * cross(v0, v2) >= 0){
return false;
}
v0 = q1 - q0;
v1 = p0 - q0;
v2 = p1 - q0;
if(cross(v0, v1) * cross(v0, v2) >= 0){
return false;
}
return true;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
debug(is_intersect({0,0}, {1,0}, {0.5,0}, {2,0}), true);
debug(is_intersect({0,0}, {1,0}, {2,0}, {3,0}), false);
debug(is_intersect({0,0}, {1,2}, {-1,1}, {10,0}), true);
debug(is_intersect({0,0}, {2,2}, {1,1}, {2,0}), true);
return 0;
}
Verified
整数バージョン(AOJなので漏れないはず)✅
typedef complex<ll> C;
ll cross(C a, C b){
return a.real() * b.imag() - a.imag() * b.real();
}
ll dot(C a, C b){
return a.real() * b.real() + a.imag() * b.imag();
}
bool is_in(C a, C b, C c){
if(a==b)return true;
if(a==c)return true;
C v0 = b-a;
C v1 = c-a;
if(cross(v0,v1)!=0)return false;
if(dot(v0,v1)<0)return true;
return false;
}
bool is_intersect(C p0, C p1, C q0, C q1){
{
if(p0==p1)return true;
if(p0==q0)return true;
if(p0==q1)return true;
if(p1==q0)return true;
if(p1==q1)return true;
if(q0==q1)return true;
}
bool is_parallel = false;
{
C v = p0-p1;
C w = q0-q1;
if(cross(v,w)==0) is_parallel=true;
}
if(is_parallel){
if(is_in(p0,q0,q1))return true;
if(is_in(p1,q0,q1))return true;
if(is_in(q0,p0,p1))return true;
if(is_in(q1,p0,p1))return true;
return false;
}
auto v0 = p1 - p0;
auto v1 = q0 - p0;
auto v2 = q1 - p0;
if(cross(v0, v1) * cross(v0, v2) > 0){
return false;
}
v0 = q1 - q0;
v1 = p0 - q0;
v2 = p1 - q0;
if(cross(v0, v1) * cross(v0, v2) > 0){
return false;
}
return true;
}