随机旋转148分求助
查看原帖
随机旋转148分求助
196903
南阳刘子骥楼主2022/9/3 15:11

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;
}
2022/9/3 15:11
加载中...