HDU - 1086-（简单几何，判断直线之间的交点）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1086

题目大意：多次输入，输入一个n，之后是n条直线（x1,y1,x2,y2）

判断这些直线有多少交点，重复的交点也算上

计算几何的基础题，向量叉乘
                AB  CD交点判断 
                相交：
                AB *AC<=0 && AB * AD>=0  所以相乘<=0 
                同理：CD *  CB<=0 && CD * CA>=0  所以相乘<=0 
          

ac：

#include<stdio.h>
#include<string.h>  
#include<math.h>  
  
//#include<map>   
//#include<set>
#include<deque>  
#include<queue>  
#include<stack>  
#include<bitset> 
#include<string>  
#include<iostream>  
#include<algorithm>  
using namespace std;  

#define ll long long  
#define INF 0x3f3f3f3f  
#define mod 1000000007
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b) 
#define clean(a,b) memset(a,b,sizeof(a))// 水印 
//std::ios::sync_with_stdio(false);
struct node{
	double x,y;
	node& operator - (node &a){
		x=x-a.x;
		y=y-a.y;
		return *this;
	}
	node (double _x=0,double _y=0):x(_x),y(_y){}
};

struct Node{
	double x1,x2,y1,y2;
}dot[110];

double cross(node a,node b)
{
	return a.x*b.y-a.y*b.x;
}

bool judge(int i,int j)
{
	if((cross(node(dot[i].x2-dot[i].x1,dot[i].y2-dot[i].y1)//第一条线 
	,node(dot[j].x1-dot[i].x1,dot[j].y1-dot[i].y1))*//第二条线 
	cross(node(dot[i].x2-dot[i].x1,dot[i].y2-dot[i].y1)//第一条线 
	,node(dot[j].x2-dot[i].x1,dot[j].y2-dot[i].y1))//第二条线 
	)<=0)
		return 1;
	else
		return 0;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int n;
	while(cin>>n&&n)
	{
		for(int i=1;i<=n;++i)
		{
			cin>>dot[i].x1>>dot[i].y1>>dot[i].x2>>dot[i].y2;
//			double x0,y0,x1,y1;
//			cin>>x0>>y0>>x1>>y1;
//			dot[i].x=fabs(x1-x0);
//			dot[i].y=fabs(y1-y0);
		}
		int ans=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=i+1;j<=n;++j)
			{
				/*
				AB  CD交点判断 
				相交：
				AB *AC<=0 && AB * AD>=0  所以相乘<=0 
				同理：CD *  CB<=0 && CD * CA>=0  所以相乘<=0 
				*/
				if(judge(i,j)&&judge(j,i))
					ans++;
			}
		}
		cout<<ans<<endl;
	}
}