ToB企服应用市场:ToB评测及商务社交产业平台

标题: P4423 [BJWC2011] 最小三角形与 SP7209 CLOSEST - Closest Triplet [打印本页]

作者: 卖不甜枣 时间: 2024-8-29 13:05
标题: P4423 [BJWC2011] 最小三角形与 SP7209 CLOSEST - Closest Triplet
noi 模仿赛 t1，所以打了些部分分，不介怀吧……
思路：

仿照平面最近点对思路，先按照横坐标排序，思量分治。
对于分割线 \(y=X\)，思量求跨过这条线的贡献，设 \(d\) 为左边和右边分治结果的最小值，则这三点中最长边的长度必须 \(\le \frac{d}{2}\)，不然不会比 \(d\) 更优。
则我们只需要思量横坐标到分割线的距离 \(\le \frac{d}{2}\) 的贡献，将这些点找出来，再按照纵坐标进排序，这里使用归并排序的话可以降一个 \(\log\)，但是没必要。
然后暴力枚举这 \(3\) 个点，使得三个点的 \(y\) 坐标的极差 \(\le \frac{d}{2}\)，然后盘算贡献即可。
时间复杂度为 \(O(N \log^2 N)\)。
P4423 [BJWC2011] 最小三角形 Code： [code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=1e6+10,INF=1e18;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)