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;
}