这道题大概也是____来的吧 qwq
平行四边形<20306>
读完题后 我么们先回顾下平行四边形的性质
两组对边相等且平行
因为题目中要求的是线段平移后的延长线
所以我们只需考虑斜率 无需关注长度
当线段的两个端点分别为(x1,y1) (x2,y2)时
其所在直线的函数解析式为
y=\frac{y1-y2}{x1-x2}x+b
(因为本题与b无关 所以在此不解出）
根据一点简单的数学常识 我们可以得到两直线平行时 其斜率相等
所以在写代码是我们只需判断两直线斜率是否相等
因为
-10^6<=x i,yi<=10^6
所以
-2e6<=k<=2e6
显然普通数组下标是无法实现的
这时就要调用map来解决这一difficulty
map<long long int,int> mp;
我们还需单独判断x1=x2这一种情况
此时x1-x2=0 (0不能做除数）
所以我们可以令此时的斜率k=2e6+1(已超出斜率上限 无需担心重复问题)
if(X1[i]==X2[i]){
mp[N]++;
}
else{
mp[(y1[i]-y2[i])/(x1[i]-x2[i])]++;
}
(其中N=2e6+1)
因为平行四边形的边是两两一组的
所以斜率为k的边能配对 map[k]/2 对
根据最大匹配公式
f(sum,max)=\begin{cases} sum/2 (sum-max>=max)\\ sum-max (sum-max<max) \end{cases}
只需判断
if(sum-maxx>=maxx){
cout<<sum/2;
}
else{
cout<<sum-maxx;
}
其中
sum=\sum_{i=1}^nmp[(y1[i]-y2[i])/(x1[i]-x2[i])]
(每次加完后都要讲mp清零 防止重复）
(当然 使用for-each遍历也是可以的）
基本框架就是这些了
具体代码就靠大家了
