题意
Link
给你 \(n\) 个点,\(1\leq x,y\leq10^9\) 。
记 \((x',y')\) 表示为 \((x+1,y)\) 或者 \((x,y+1)\)
定义一对点合法 \((x_1,y_1),(x_2,y_2)\) 当且仅当存在 \((x_1',y_1'),(x_2',y_2')\)
使得\((x_1',y_1'),(x_2',y_2'),(0,0)\)
共线。
问最多能选出多少对点，注意：一个点最多只能被选择一次。
题解
很显然如果 \((x_1,y_1),(x_2,y_2)\)
与 \((0,0)\)
贡献，当且仅当这两个点斜率相同，即 \(\frac{y_1}{x_1}=\frac{y_2}{x_2}\)。
而这个 \(\frac{x_1}{y_1}\) 相当于
这个点的属性值。
那么问题转换为给你 \(n\)
个点，每个点有两种可能的属性值。
让你每次选出两个存在相同属性的点，问最多选多少个。
我最初的想法是想把 这个平面上的 \((x,y)\) 看成点，而选择一对 \((x,y)\) 看成一个类似匹配的东西。
但是 1.5h
我也没什么有价值的idea。（如果能类似这么做还请大佬不吝赐教）
正解是这样的，我们把 斜率看成点，而把这个 \((x,y)\) 看成连接两个可能的斜率的边。
我们发现，两个移动后可能共线的 \((x,y)\)
必定是图中连接3个点的两条边，也就是至少有一个公共点的两条边。
现在做法应该比较明晰了。
注意我们的匹配不是针对点的，而是针对边的。
具体做法是建出 \(dfs\)
树，我们把结点连向儿子的边匹配，如果剩下一条边的话 即 \(sz_x\bmod 2=1\)。我们就将剩下这条与 \((x\rightarrow son_x)\) 这条边匹配，并且在
\(fa_x\) 的匹配时不计算这条边。
容易发现这样匹配一定是最优的。
\(why?\)
考虑如果没有全部匹配，一定是只剩下 \(root\rightarrow son_r\)
这一条边。那么发现总边数也一定是奇数，不存在全部匹配的情况。
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
| #include<bits/stdc++.h>
using namespace std;
int n;
#define int long long
const int N=2e5+10000;
int a[N],b[N],c[N],d[N];
struct frac{int a,b;};
inline bool operator < (frac a,frac b){
if(a.a==b.a) return a.b<b.b;
return a.a<b.a;
}
inline int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
inline frac operator / (frac a,frac b){
frac c;
c.a=a.a*b.b;
c.b=a.b*b.a;
int g=gcd(c.a,c.b);
c.a/=g,c.b/=g;
return c;
}
map<frac,int> mp;
frac x,y,f[N][5];
struct node{int x,v;};
inline bool operator <(node a,node b){
if(a.v==b.v) return a.x<b.x;
return a.v<b.v;
}
vector<pair<int,int> > ans,v[N<<2];
int tot;bool vis[N<<2];
int dep[N<<2];
inline void dfs(int x,int fa,int faid)
{
dep[x]=dep[fa]+1;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,w=v[x][i].second;
if(dep[y]==0) dfs(y,x,w);
}
int pre=0;
for(int i=0;i<v[x].size();i++){
int y=v[x][i].first,w=v[x][i].second;
if(dep[y]>dep[x]){
if(vis[w]) continue;
if(pre==0) pre=w;
else{
vis[pre]=vis[w]=1;
ans.push_back(make_pair(pre,w));
pre=0;
}
}
}
if(pre&&faid){
vis[pre]=vis[faid]=1;
ans.push_back(make_pair(pre,faid));
}
}
signed main(){
ios::sync_with_stdio(false);
cin>>n;
int id=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i]>>d[i];
x=frac{a[i]+b[i],b[i]};
y=frac{c[i],d[i]};
f[i][1]=x/y;
x=frac{a[i],b[i]};
y=frac{c[i]+d[i],d[i]};
f[i][2]=x/y;
for(int k=1;k<=2;++k){
if(mp[f[i][k]]==0) {tot++,mp[f[i][k]]=tot;continue;}
}
v[mp[f[i][1]]].push_back(make_pair(mp[f[i][2]],i));
v[mp[f[i][2]]].push_back(make_pair(mp[f[i][1]],i));
}
for(int i=1;i<=tot;i++) if(dep[i]==0) dfs(i,0,0);
cout<<ans.size()<<endl;
for(auto x:ans){
cout<<x.first<<" "<<x.second<<endl;
}
}
|