[poj 1066][洛谷UVA 754]Treasure Hunt{2つの線分が交差しているか否かを判断する}

タイトル
https://www.luogu.org/problemnew/show/UVA754 http://poj.org/problem?id=1066
問題を解く構想. … … CE了,求助!!!CEだ、助けて!!!CEだ、助けて!!!
境界の任意の取点で目標点に接続し、どれだけのエッジと交差するかを尋ねるという意味を通俗的に理解することができます.
2本の線分が交わるか否かを判断する条件:(Cproduct(b 1,b 2,c 1,c 2,a 1,a 2)*Cproduct(b 1,b 2,d 1,d 2,a 1,a 2)<0&&Cproduct(d 1,d 2,b 1,b 2,c 1,c 2)*Cproduct(d 1,d 2,a 2,a 2,c 2)*Cproduct(d 1,d 2,a 1,a 2,c 1,c 2)<0)
コード#コード#

#include
#define db double 
using namespace std; 
const int maxn=50; 
const int Inf=0x3f3f3f3f; 
const db Err=1e-8; 
inline int minn(int x,int y){return x<y?x:y;} 
int T,n; 
struct Vec{
    db x,y; db operator * (const Vec& oth)const {return x*oth.y-y*oth.x;}
};
struct Point{
    db x,y; Vec operator - (const Point& oth)const {return (Vec){x-oth.x,y-oth.y};}
}a[maxn],b[maxn],P;
int Solve(Point A,Point B){
    int ret=0; Vec AB=B-A; 
    for (int i=1;i<=n;++i) {
        Vec AC=a[i]-A,AD=b[i]-A,CD=b[i]-a[i],CB=B-a[i]; 
        if ((AB*AC)*(AB*AD)<-Err&&(CD*AC)*(CD*CB)>Err) ret++; 
    }
    return ret; 
}
int main(){
    scanf("%d",&T); 
    while (T--){
    scanf("%d",&n); int ans=Inf; 
    for (int i=1;i<=n;++i) scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&b[i].x,&b[i].y); 
    scanf("%lf%lf",&P.x,&P.y); 
    for (int i=1;i<=n;++i) ans=minn(ans,Solve(a[i],P)),ans=minn(ans,Solve(b[i],P)); 
    if (!n) ans=0; 
    printf("Number of doors = %d
",ans+1); 
    if (T) printf("
"); 
    }
    return 0; 
}