随机旋转148分求助

P7883 平面最近点对(加强加强版)

南阳刘子骥 @ 2022-09-03 15:11:32

rt
两个点都是WA,说“Wrong answer on Line 1 Colomn 4, found 6, expected 5”。
怀疑是精度问题,使用了long double之后仍然WA。
代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld double
const int N = 400010;
const ld pi = 3.141592653589793238462643383279;
int n, m;
ld ans = 1e18;
struct Point
{
    ld x, y;
    Point() {};
    Point(ld _x, ld _y) { this->x = _x, this->y = _y; }
    bool operator < (const Point &a)const
    {
        return x * y < a.x *a.y;
    }
};
Point a[N];
ld dis(Point u, Point v)
{
    return (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y);
}
void calc()
{
    sort(a + 1, a + 1 + n);
    for(int i = 2; i <= n; i++)
        for(int j = i - 1; j >= i - 50 && j >= 1; j--)
            ans = min(ans, dis(a[i], a[j]));
}
void spin(ld o)
{
    o = o / 180.0 * pi;
    for(int i = 1; i <= n; i++)
    {
        ld x = a[i].x, y = a[i].y;
        ld xn = x * cos(o) - y * sin(o);
        ld yn = x * sin(o) + y * cos(o);
        a[i] = { xn,yn };
    }
}
int main()
{
    const char endl = '\n';
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    calc();
    spin(rand() % 360);
    calc();
    printf("%.0lf\n", ans);
    return 0;
}

by _Winham_ @ 2022-09-03 15:23:09

你精度问题用long double也不行呀


by Iwara_qwq @ 2022-09-03 15:34:35

请用分治


by luogu_gza @ 2022-10-04 12:19:18

@南阳刘子骥 pi改成acos(-1)试试看


by 南阳刘子骥 @ 2022-10-04 14:08:45

@acwing_gza

理论上不行,因为acos的精度没有手写高。

实际上仍然不行,仍然是148分。


by luogu_gza @ 2022-10-09 16:00:14

@南阳刘子骥 感觉rand不行,你换mt19937试试看


by 南阳刘子骥 @ 2022-10-09 16:37:15

@acwing_gza 148分变成146分了……


by luogu_gza @ 2022-10-09 16:39:57

@南阳刘子骥 我吐了,可不可以交你的代码我去调一调?


by 南阳刘子骥 @ 2022-10-09 16:40:39

@acwing_gza 调罢……
我已经不会了……


by Fish_Clever @ 2022-10-11 20:03:44

正解又不是这个...考试时或可以这么写,但这个的正确性没有证明吧.


by __BAI__ @ 2022-10-23 08:22:43

@南阳刘子骥 50太小了,取80试试


| 下一页