CCPC-Wannafly Winter Camp Day5 (Div2, onsite) J Special Judge 边与边的关系

J - Special Judge

对任意两条边都进行判断是否相交，如果相交则在判断是否是相交于端点，不过不是则ans++。是的话在判断下是不是重合边，如果不是重合边就不符合，是就ans++.

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	double x;
	double y;
};
bool judge(node a,node b,node c,node d)
{
	if(min(a.x,b.x) <= max(c.x,d.x) && min(c.x,d.x) <= max(a.x,b.x) && min(a.y,b.y) <= max(c.y,d.y) &&min(c.y,d.y)<=max(a.y,b.y))
	{

		double u,v,w,z;//保存叉乘
          u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
          v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
          w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
          z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
          return (u*v<=0.00000001 && w*z<=0.00000001); //浮点数判断大小
	}
	return false;
}
bool onsegment(node pi,node pj,node Q)
{
    if((Q.x-pi.x)*(pj.y-pi.y)==(pj.x-pi.x)*(Q.y-pi.y)&&min(pi.x,pj.x)<=Q.x&&Q.x<=max(pi.x,pj.x)&&min(pi.y,pj.y)<=Q.y&&Q.y<=max(pi.y,pj.y)){
        return true;
    }else{
        return false;
    }
}
bool check(node a,node b,node c,node d){
    double len=(a.x-b.x)*(c.y-d.y)-(c.x-d.x)*(a.y-b.y);
    if(len==0)return 1;
    else return 0;
}
const int maxn=1020;
struct Node{
    int a,b;
}mp[2*maxn];
node p[maxn];
int main(){
    int n,m;
    int ans=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&mp[i].a,&mp[i].b);
    }
    for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
    for(int i=1;i<=m;i++){
        for(int j=i+1;j<=m;j++){
                if(judge(p[mp[i].a],p[mp[i].b],p[mp[j].a],p[mp[j].b])){
                    if(mp[i].a==mp[j].a||mp[i].a==mp[j].b||mp[i].b==mp[j].a||mp[i].b==mp[j].b){	//判断是否是交于端点
                        if(check(p[mp[i].a],p[mp[i].b],p[mp[j].a],p[mp[j].b])){	//看两边是否平行
								//如果平行，通过判断一边的两端点是否在另外一边上
                                if((onsegment(p[mp[j].a],p[mp[j].b],p[mp[i].a])&&onsegment(p[mp[j].a],p[mp[j].b],p[mp[i].b]))||(onsegment(p[mp[i].a],p[mp[i].b],p[mp[j].a])&&onsegment(p[mp[i].a],p[mp[i].b],p[mp[j].b])))
                                ans++;
                        }
                    }
                    else ans++;
                }
        }
    }
    printf("%d\n",ans);
	return 0;
}