南阳刘子骥 @ 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试试