2020河北省程序设计竞赛—连杀（几何，搜索）

河北省程序设计竞赛—连杀（几何，搜索）"/>

2020河北省程序设计竞赛—连杀（几何，搜索）

2020河北省程序设计竞赛的一道题：连杀

意思就是，在平面上给出15个以内的点，问至少需要几条直线，可以把所有点覆盖

思路：

枚举所有点连接成的直线，然后找到所有在这条直线上的点，放入map<pair<int,int>,vector<int>> mp里，其中<pair<int,int>是通过2个点 t 1 t_{1} t1​， t 2 t_{2} t2​的编号来锁定这条直线，vector<int>存储这条直线上的点（不包括 t 1 t_{1} t1​， t 2 t_{2} t2​，其实存了也没事），这个过程 O ( n 3 ) O(n^3) O(n3)

需要注意的是，浮点数类型可能因为精度不够而无法足够精确地表示每一个斜率，因此我们需要换一种方法来记录斜率，一般情况下，斜率可以表示为 slope = Δ y Δ x \textit{slope} = \dfrac{\Delta y}{\Delta x} slope=ΔxΔy​的形式，因此我们可以用分子和分母组成的二元组来代表斜率。但注意到存在形如 1 2 = 2 4 \dfrac{1}{2}=\dfrac{2}{4} 21​=42​这样两个二元组不同，但实际上两分数的值相同的情况，所以我们需要将分数 Δ y Δ x \dfrac{\Delta y}{\Delta x} ΔxΔy​化简为最简分数的形式 m y m x \dfrac{my}{mx} mxmy​

将分子和分母同时除以二者绝对值的最大公约数，可得二元组 ( Δ x gcd ⁡ ( ∣ Δ x ∣ , ∣ Δ y ∣ ) , Δ y gcd ⁡ ( ∣ Δ x ∣ , ∣ Δ y ∣ ) ) \Big(\dfrac{\Delta x}{\gcd(|\Delta x|,|\Delta y|)},\dfrac{\Delta y}{\gcd(|\Delta x|,|\Delta y|)}\Big) (gcd(∣Δx∣,∣Δy∣)Δx​,gcd(∣Δx∣,∣Δy∣)Δy​)，令 mx = Δ x gcd ⁡ ( ∣ Δ x ∣ , ∣ Δ y ∣ ) \textit{mx}=\dfrac{\Delta x}{\gcd(|\Delta x|,|\Delta y|)} mx=gcd(∣Δx∣,∣Δy∣)Δx​， my = Δ y gcd ⁡ ( ∣ Δ x ∣ , ∣ Δ y ∣ ) \textit{my}=\dfrac{\Delta y}{\gcd(|\Delta x|,|\Delta y|)} my=gcd(∣Δx∣,∣Δy∣)Δy​则上述化简后的二元组为 ( mx , my ) (\textit{mx},\textit{my}) (mx,my)，此外，因为分子分母可能存在负数，为了防止出现形如 − 1 2 = 1 − 2 \dfrac{-1}{2}=\dfrac{1}{-2} 2−1​=−21​，的情况，我们还需要规定分子为非负整数，如果 mx \textit{mx} mx 为负数，我们将二元组中两个数同时取相反数即可

特别地，考虑到 m x mx mx 和 m y my my 两数其中有且仅有有一个为 0 的情况（因为题目中可能存在重复的点，所以我们在读入数据的时候做处理，不会出现两个都为0的情况，即两点重合），此时两数不存在数学意义上的最大公约数，因此我们直接特判这两种情况。

• 当 m x mx mx 为 0 时，我们令 m y = 1 my=1 my=1（斜率不存在）， m x = 0 mx=0 mx=0
• 当 m y my my 为 0 时，我们令 m x = 1 mx=1 mx=1（斜率为0）， m y = 0 my=0 my=0

经过上述操作之后，即可得到最终的表示斜率的二元组 ( mx , my ) (\textit{mx},\textit{my}) (mx,my)

然后dfs每一种可能的连线，如果加入了这条线，就把这条线上的所有点标记vis=1，在回溯的时候用vis=0取消标记，dfs如果发现当前ans已经大于了res，直接return就好，注意只剩下最后一个点时，没有其他点可以与之匹配，此时直接更新结果即可

代码：

#include<bits/stdc++.h>
#define pb push_back
#define in insert
#define mem(f, x) memset(f,x,sizeof(f))
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;typedef pair<int,int>PII;
typedef pair<long,long>PLL;typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,M=1e9+7;
const int inf=1e9+7;struct node{int x,y;
}a[16];map<pair<int,int>,vector<int>> mp;
int n,ans=0,res=inf;int gcd(int x,int y){if(x==0)return 1;return y?gcd(y,y%x):x;
}void f(int t1,int t2){pair<int,int> p1,p2;//t1与t2的斜率存入p1int y=a[t1].y-a[t2].y,x=a[t1].x-a[t2].x;int g=gcd(abs(y),abs(x));if(!x){//垂直于x轴的一条直线//相对的x=0,y!=0p1={1,0};}else if(!y){//平行于x轴的一条直线//相对的x!=0,y=0p1={0,1};}else{if(y < 0)p1={-y/g,-x/g};else p1={y/g,x/g};}//t1与其他点的斜率存入p2for(int i=1;i<=n;i++){if(i!=t1&&i!=t2){int y=a[i].y-a[t1].y,x=a[i].x-a[t1].x;int g=gcd(abs(y),abs(x));if(!x)p2={1,0};else if(!y)p2={0,1};else{if(y < 0)p2={-y/g,-x/g};else p2={y/g,x/g};}//如果t1t2上有其他点，就把它加入映照容器if(p1==p2){mp[{t1,t2}].push_back(i);}}}
}int vis[16];void ak(int x,int y){//连接for(auto i:mp[{x,y}]){vis[i]=1;}
}
void ak2(int x,int y){//取消连接for(auto i:mp[{x,y}]){vis[i]=0;}
}
void dfs(){int p=0;if(ans<res){for(int i=1;i<=n;i++){if(!vis[i])p++;}//特殊处理只有一个点的情况if(p==1){res=min(ans+1,res);return ;}else if(p==0){res=ans;return ;}}if(ans>=res)return ;int p1=0,p2=0;for(int i=1;i<=n;i++){if(!vis[i]&& !p1)p1=i;else if(!vis[i]&& p1 && !p2) p2=i;if(p1&&p2)break;}//因为两点连线是小的编号在前if(p1>p2)swap(p1,p2);ak(p1,p2);vis[p1]=1;vis[p2]=1; ans++;dfs();ak2(p1,p2);vis[p1]=0;vis[p2]=0;ans--;
}
set<pair<int,int>> st;
int main(){cin>>n;if(n<=2){cout<<1<<endl;return 0;}for(int i=1;i<=n;i++){int t1,t2;cin>>t1>>t2;//找到了重合的点if(st.find({t1,t2})!=st.end()){n--,i--;continue;}st.insert({t1,t2});a[i].x=t1;a[i].y=t2;}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){f(i,j);}}dfs();cout<<res<<endl;return 0;
}
/*
5
1 1
1 2
1 3
2 2
3 22
*/
/*
4
-1 1
1 1
2 0
2 22
*/
/*
3
0 1
0 -1
0 01
*/

类似的也有一道题：直线上最多的点数，就简单多了