crazy_cloud's Blog
0%

CS Academy Round 38 Parallel Lines

Posted on Edited on In

题目大意

给定平面上的 \(n\) 个点，请使用最少的互相平行的直线覆盖所有的点。 保证答案 \(K\) 不超过 \(400\)。

\(1\leq n\leq 3\times10^4\)

题目分析

考虑对 \(K\) 与 \(n\) 的大小关系分类讨论：

\(n\leq 2K\)

这时我们显然可以直接写一个 \(n^2\) 的暴力算法：将所有点对斜率存下来，然后枚举不同的斜率，使用并查集将某种斜率连接的点并起来，最后连通块的个数就是我们要的答案。

时间复杂度 \(O(n^2\alpha(n)\times hashset)\)。

\(n>2K\)

可以发现，既然答案不超过 \(K\)，那么我们所要求的斜率一定在前 \(K\) 个点两两之间组成的点对中出现了至少 \(K\) 次：在 \(K=2n\) 时最坏的情况就是每条直线都穿过了两个点，这已经出现了 \(K\) 次了，在 \(n>2K\) 时只会更多。

于是我们对所有出现次数超过 \(K\) 次的进行检查，次数是 \(O(K)\) 的。

时间复杂度 \(O(nK\times hashset)\)。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long LL;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=30005;
const int K=400;
const int M=(K<<1)+5;
const int L=M*M;

typedef pair<int,int> P;
typedef pair<P,P> PI;
#define mkp(a,b) make_pair(a,b)
#define ft first
#define sd second

int x[N],y[N],a[N],fa[N],rk[N],reach[N];
PI list[L];
LL srt[N];
int T,n,m,cnt,ans,ti;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

int getfather(int son)
{
	if (reach[son]!=ti) return reach[son]=ti,rk[son]=0,fa[son]=son;
	else return fa[son]==son?son:fa[son]=getfather(fa[son]);
}

inline bool merge(int x,int y)
{
	x=getfather(x),y=getfather(y);
	if (x==y) return 0;
	if (rk[x]<rk[y]) swap(x,y);
	return fa[y]=x,rk[x]+=rk[x]==rk[y],1;
}

int main()
{
	freopen("par.in","r",stdin),freopen("par.out","w",stdout);
	for (T=read();T--;)
	{
		n=read();
		for (int i=1;i<=n;++i) x[i]=read(),y[i]=read();
		m=min(K*2,n),cnt=0;
		for (int i=1;i<=m;++i)
			for (int j=1;j<i;++j)
			{
				int x_=x[i]-x[j],y_=y[i]-y[j];
				if (x_<0||!x_&&y_<0) x_*=-1,y_*=-1;
				int g=gcd(abs(x_),abs(y_));
				list[++cnt]=mkp(mkp(y_/g,x_/g),mkp(j,i));
			}
		sort(list+1,list+1+cnt),ans=n;
		for (int st=1,en;st<=cnt;st=en)
		{
			for (en=st;en<=cnt&&list[st].ft==list[en].ft;++en);
			if (n<=K*2)
			{
				int cur=n;++ti;
				for (int i=st;i<en;++i) cur-=merge(list[i].sd.ft,list[i].sd.sd);
				ans=min(ans,cur);
			}
			else if (en-st>=K)
			{
				int p=list[st].ft.ft,q=list[st].ft.sd;
				for (int i=1;i<=n;++i) srt[i]=1ll*p*x[i]-1ll*q*y[i];
				sort(srt+1,srt+1+n),ans=min(ans,(int)(unique(srt+1,srt+1+n)-(srt+1)));
			}
		}
		printf("%d\n",ans);
	}
	fclose(stdin),fclose(stdout);
	return 0;
}