C++11(clang++ 3.9) 解法, 执行用时: 299ms, 内存消耗: 872K, 提交时间: 2020-01-04 18:50:31

#include <bits/stdc++.h>
using namespace std;
int f[100005],mk[100005],ans;
struct node
{
	long long x,y;
}a[100005];
struct line
{
	node a,b;
}l[100005];
int check(line xx,line yy)
{
	node a=xx.a,b=xx.b,c=yy.a,d=yy.b;
	if(!(min(a.x,b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x) && min(a.y,b.y)<=max(c.y,d.y)))
	return 0;
	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);
}
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
int main()
{
	int n,p=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		f[i]=i;
		scanf("%lld%lld",&a[p].x,&a[p].y);
		p++;
		scanf("%lld%lld",&a[p].x,&a[p].y);
		l[i]=(line){a[p-1],a[p]};
		p++;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	if(i!=j)
	{
		if(check(l[i],l[j]))
		f[find(i)]=find(j);
	}
	for(int i=1;i<=n;i++)
	if(!mk[find(i)])
	mk[find(i)]=1,ans++;
	printf("%d",ans);
}

C++14(g++5.4) 解法, 执行用时: 137ms, 内存消耗: 732K, 提交时间: 2019-12-28 15:52:21

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e3+5;
struct Point {
	ll x,y;
}p[N][2];
bool check(Point a,Point b,Point c,Point 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))) return false;
    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<=1e-9&&w*z<=1e-9;
}
int f[N];
int Find(int x) {
	if(x==f[x]) return x;
	return f[x]=Find(f[x]);
}
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%lld%lld%lld%lld",&p[i][0].x,&p[i][0].y,&p[i][1].x,&p[i][1].y);
		f[i]=i;
	}
	for(int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			if(check(p[i][0],p[i][1],p[j][0],p[j][1])) f[Find(i)]=Find(j);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) {
		if(Find(i)==i) ans++;
	}
	printf("%d\n",ans);
	return 0;
}