G50 叉积应用 线线关系【计算几何】

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
const double eps=1e-10;
const int N=1e5+10;
struct Point
{
	double x,y;
	Point(){}
	Point(double a,double b){x=a;y=b;}
	void input(){scanf("%lf%lf",&x,&y);}
	friend Point operator+(const Point &a,const Point &b){return {a.x+b.x, a.y+b.y};}
	friend Point operator-(const Point &a,const Point &b){return {a.x-b.x, a.y-b.y};}
	friend Point operator*(const Point &a,const double &k){return {a.x*k, a.y*k};}
	friend Point operator/(const Point &a,const double &k){return {a.x/k, a.y/k};}
	friend double det(const Point &a,const Point &b){return a.x*b.y-a.y*b.x;}
};
struct Line
{
	Point a,b;
	Line(){}
	Line(Point x,Point y):a(x),b(y){}
	friend bool Point_in_Line(Point p,Line L)
	{
		return (p.x-L.a.x)*(p.x-L.b.x)<eps &&
		       (p.y-L.a.y)*(p.y-L.b.y)<eps;
	}
	friend bool parallel(Line L1,Line L2){ return fabs( det(L2.b-L2.a, L1.b-L1.a) )<eps;}
	
	friend Point Line_make_Point(Line L1,Line L2)
	{
		Point a=L1.a, b=L1.b, c=L2.a, d=L2.b;
		double s1=det(c-a, b-a);
		double s2=det(d-a, b-a);
		return (c*s2 - d*s1)/(s2 - s1);
	}
	friend bool intersect(Line L1,Line L2)
	{
		if( parallel(L1, L2) )
		{
			return (Point_in_Line(L2.a, L1) || 
			        Point_in_Line(L2.b, L1) ||
					Point_in_Line(L1.a, L2) ||
					Point_in_Line(L1.b, L2))
					&& fabs(det(L1.b-L1.a, L2.b-L1.a))<eps;
		}
		else 
		{
			Point p=Line_make_Point(L1, L2);
			return Point_in_Line(p, L1)&&Point_in_Line(p, L2);
		}	
	}
}L[N];
int ans[N],cnt,v[N]; 
int main()
{
	int n;scanf("%d",&n);
	for(int i=1; i<=n; i++)L[i].a.input(),L[i].b.input();
	memset(v,0,sizeof(v));
	for(int i=1; i<=n; i++)
	{
		for(int j=i+1; j<=n; j++)
			if(intersect(L[i],L[j])) 
			{
				v[i]=1;
				break;
			}
	}
	for(int i=1; i<=n; i++)if(!v[i]) printf("%d ",i);
	return 0;
}