题解：P10459 Raid

· · 题解

P10459 Raid 题解

我们充分发扬人类智慧：

将所有点全部绕原点旋转同一个角度，然后按 x \times y 排序。

根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远。

所以我们只取每个点向前的 500 个点来计算答案。

这样速度快得飞起，在 n=100000 时都可以在 1s 内卡过。

AC code：(代码风格可能有点奇怪)

#include<bits/stdc++.h>
#define AC 0
#define D(x) cout<<#x<<": "<<x<<endl
#define IOS ios::sync_with_stdio(false), cin.tie(), cout.tie()
#define RE register
#define int long long
#define fst first
#define scd second
#define mkp make_pair
#define inl inline
#define up(l,r,i) for(RE int i=l,END##i=r;i<=END##i;i=-~i)
#define dn(r,l,i) for(RE int i=r,END##i=l;i>=END##i;i=~-i)
#define mems(a, x) memset((a), (x), sizeof(a))
#define Open(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define eb emplace_back
using namespace std;
inline int max(int a, int b){return a < b ? b : a;}
inline int min(int a, int b){return a < b ? a : b;}
inline int ksm(int a, int m){int ans=1;while(m){if(m & 1) ans *= a;a *= a;m >>= 1;}return ans;}
inline int ksm(int a, int m, int p){int ans=1;while(m){if(m & 1) ans = (ans * a) % p;a = (a * a) % p;m >>= 1;}return ans;}
inline int read() {int x = 0;bool f = 1;char ch = getchar();while (!isdigit(ch)) f = ch == '-' ? 0 : 1, ch = getchar();while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();return f ? x : -x;}
inline void write(int x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + 48);}
const int N = 1e6 + 7;
const double Pi = 3.141592653589732;
struct node{
    double x, y;
    bool flag;
}a[N];
int T, n;
double ans;
inline node Rotate(node a, double rad, bool fff){
    return node{a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad), fff};
}
inline bool cmp(const node &x, const node &y){return x.x * x.y < y.x * y.y;}
inline double Dis(node a, node b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
inline void getAns(){
    up(1, n, i){
        for(int j = 1; j <= 500 && i + j <= n; j = -~j){
            if(a[i + j].flag ^ a[i].flag){
//              if(ans > Dis(a[i], a[i + j])){
//                  cout << i + j << '\n';
//              }
                ans = min(ans, Dis(a[i], a[i + j]));
            }
        }
    }
}
double rad[] = {Pi / 0.6, Pi / 0.3, Pi / 0.5};
signed main() {
//  Open("data");
    cin >> T;
    srand(time(0));
    while(T--){
        ans = 1e18;
        cin >> n;
        int rnd = 0;
        up(1, n, i) cin >> a[i].x >> a[i].y, a[i].flag = 0;
        up(1, n, i) cin >> a[i + n].x >> a[i + n].y, a[i + n].flag = 1;
        n <<= 1;
        up(0, 2, i){
            sort(a + 1, a + 1 + n, cmp);
//          up(1, n, k) cout << a[k].x << ' ' << a[k].y << ' ' << a[k].flag << '\n';
            getAns();
            up(1, n, k) a[k] = Rotate(a[k], rad[i], a[k].flag);
        }
        sort(a + 1, a + 1 + n, cmp);
        getAns();
        printf("%.3lf\n", ans);
    }
    return AC;
}

update：

2025.1.20： 修改代码通过 hack 数据。

另附练习题目 P1257 P1429 P7883。

致敬万谔之源。

留个赞再走呗。