骗分技巧
参考资料
人类智慧
洛谷 P7883 平面最近点对（加强加强版）
给定平面上 个的点，求距离最近的两个点的距离。
提示
我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 排序。
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远。
所以我们只取每个点向前的 个点来计算答案。
这样速度快得飞起，在 时都可以在 内卡过。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const double pi=acos(-1.0);
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=400005;
struct Point
{
double x,y;
}a[N];
bool cmp(Point u,Point v)
{
return u.x*u.y<v.x*v.y;
}
double dis2(Point u,Point v)
{
return (u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
random_device rd;
mt19937 gen(rd());
uniform_real_distribution<> dist(0,pi*2);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
double r=dist(gen);
for(int i=1;i<=n;i++)
{
double x=a[i].x,y=a[i].y;
a[i].x=x*cos(r)-y*sin(r);
a[i].y=x*sin(r)+y*cos(r);
}
sort(a+1,a+n+1,cmp);
double ans=inf;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=min(i+100,n);j++)
{
ans=min(ans,dis2(a[i],a[j]));
}
}
cout<<(ll)(ans+0.5)<<'\n';
return 0;
}
洛谷 P1452 【模板】旋转卡壳 | [USACO03FALL] Beauty Contest G
给定平面上 个点，求凸包直径。
提示
我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 排序。
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太近。
所以我们只取最远点以及向前的 个点来计算答案。
这样速度快得飞起，在 时都可以在 内卡过，hack 数据都起不到效果。
#include <bits/stdc++.h>
using namespace std;
const int N=50005;
struct Point
{
int x,y;
}a[N];
bool cmp(Point u,Point v)
{
return u.x*u.x+u.y*u.y<v.x*v.x+v.y*v.y;
}
int dis2(Point u,Point v)
{
return (u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=max(1,n-4);j<=n;j++)
{
ans=max(ans,dis2(a[i],a[j]));
}
}
cout<<ans<<'\n';
return 0;
}
洛谷 P6247 [SDOI2012] 最近最远点对
给定平面上 个点，分别求出距离最近的两个点的距离和距离最远的两个点的距离。
提示
我们充分发扬人类智慧：
将所有点按 排序。
根据数学直觉，在排序后，最近的两个点在数组中肯定不会离得太远，最远的两个点在数组中肯定不会离得太近。
所以只取每个点向后的 个点更新最近距离，并取最后向前的 个点更新最远距离。
这样速度快得飞起，直接拿到了此题的最优解。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=100005;
struct Point
{
double x,y;
}a[N];
bool cmp(Point a,Point b)
{
return a.x<b.x;
}
double dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
double mn=inf,mx=0;
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=min(i+20,n);j++)
{
mn=min(mn,dis(a[i],a[j]));
}
for(int j=1;j<=min(20,n);j++)
{
mx=max(mx,dis(a[i],a[j]));
}
for(int j=max(1,n-20);j<=n;j++)
{
mx=max(mx,dis(a[i],a[j]));
}
}
cout<<fixed<<setprecision(2)<<mn<<' '<<mx<<'\n';
return 0;
}