P4423 [BJWC2011] 最小三角形 与 SP7209 CLOSEST
cnblogs 2024-08-29 14:39:00 阅读 94
![P4423 [BJWC2011] 最小三角形 与 SP7209 CLOSEST - Closest Triplet](/uploads/2024/08/29/1724913541392091903.webp)
讲解 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<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#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<=r;i++)
#define _For(i,l,r) for(int i=r;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<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Point{
db x,y;
friend bool operator==(const Point &a,const Point &b){
return a.x==b.x&&a.y==b.y;
}
friend db dis(const Point &a,const Point &b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
}a[N];
ll n,sum;
namespace Sub1{
db ans=INF;
void work(){
For(i,1,n)
For(j,i+1,n)
For(k,j+1,n)
ans=min(ans,dis(a[i],a[j])+dis(a[j],a[k])+dis(a[i],a[k]));
printf("%.10lf\n",ans);
}
};
namespace Sub2{
db ans=INF;
bool cmp(Point &a,Point &b){
return a.x<b.x;
}
void work(){
sort(a+1,a+n+1,cmp);
For(i,1,n-2)
ans=min(ans,dis(a[i],a[i+1])+dis(a[i+1],a[i+2])+dis(a[i],a[i+2]));
printf("%.10lf\n",ans);
}
};
namespace Sub3{
ll cnt=0;
Point b[N];
db ans=INF;
bool cmp1(Point &a,Point &b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
bool cmp2(Point &a,Point &b){
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
db solve(ll l,ll r){
if(l==r)
return INF;
ll mid=(l+r)>>1;
ll I=a[mid].x;
db d=min(solve(l,mid),solve(mid+1,r));
cnt=0;
For(i,l,r)
if(abs(a[i].x-I)<=d/2)
b[++cnt]=a[i];
sort(b+1,b+cnt+1,cmp2);
For(i,1,cnt){
For(j,i+1,cnt){
if(b[j].y-b[i].y>d/2)
break;
For(k,j+1,cnt){
if(b[k].y-b[i].y>d/2)
break;
d=min(d,dis(b[i],b[j])+dis(b[i],b[k])+dis(b[j],b[k]));
}
}
}
return d;
}
void work(){
sort(a+1,a+n+1,cmp1);
printf("%.10lf\n",solve(1,n));
}
};
int main(){
open("A.in","A.out");
n=read();
For(i,1,n){
a[i]={(db)read(),(db)read()};
sum+=a[i].y;
}
if(n<=100)
Sub1::work();
else if(!sum)
Sub2::work();
else
Sub3::work();
return 0;
}
SP7209 CLOSEST - Closest Triplet Code：
#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#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<=r;i++)
#define _For(i,l,r) for(int i=r;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=2e5+10,INF=1e18;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
struct Point{
db x,y;
friend bool operator==(const Point &a,const Point &b){
return a.x==b.x&&a.y==b.y;
}
friend db dis(const Point &a,const Point &b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
}a[N];
ll n,sum;
namespace Sub1{
db ans=INF;
void work(){
For(i,1,n)
For(j,i+1,n)
For(k,j+1,n)
ans=min(ans,dis(a[i],a[j])+dis(a[j],a[k])+dis(a[i],a[k]));
printf("%.3lf\n",ans);
}
};
namespace Sub2{
db ans=INF;
bool cmp(Point &a,Point &b){
return a.x<b.x;
}
void work(){
sort(a+1,a+n+1,cmp);
For(i,1,n-2)
ans=min(ans,dis(a[i],a[i+1])+dis(a[i+1],a[i+2])+dis(a[i],a[i+2]));
printf("%.3lf\n",ans);
}
};
namespace Sub3{
ll cnt=0;
Point b[N];
db ans=INF;
bool cmp1(Point &a,Point &b){
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
bool cmp2(Point &a,Point &b){
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
db solve(ll l,ll r){
if(l==r)
return INF;
ll mid=(l+r)>>1;
ll I=a[mid].x;
db d=min(solve(l,mid),solve(mid+1,r));
cnt=0;
For(i,l,r)
if(abs(a[i].x-I)<=d/2)
b[++cnt]=a[i];
sort(b+1,b+cnt+1,cmp2);
For(i,1,cnt){
For(j,i+1,cnt){
if(b[j].y-b[i].y>d/2)
break;
For(k,j+1,cnt){
if(b[k].y-b[i].y>d/2)
break;
d=min(d,dis(b[i],b[j])+dis(b[i],b[k])+dis(b[j],b[k]));
}
}
}
return d;
}
void work(){
sort(a+1,a+n+1,cmp1);
printf("%.3lf\n",solve(1,n));
}
};
int main(){
while(1){
n=read();
if(n==-1)
break;
For(i,1,n){
a[i]={(db)read(),(db)read()};
sum+=a[i].y;
}
if(n<=100)
Sub1::work();
else if(!sum)
Sub2::work();
else
Sub3::work();
}
return 0;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。