DDDreamer @ 2021-06-26 17:43:01
使用这个代码生成
#include <cmath>
#include <cstdio>
using namespace std;
const double DEGPAI = atan( 1.0 ) / 45.0;
int main() {
freopen( "p1429_hack.txt", "w", stdout );
printf( "%d\n", 360 * 10 + 2 );
printf( "%lf %lf\n%lf %lf\n", 0, 0, cos( DEGPAI * 0.5 ), sin( DEGPAI * 0.5 ) );
for( int i = 0; i < 360; ++i ) {
double qx = cos( DEGPAI * i ), qy = sin( DEGPAI * i );
for( int j = 60; j < 80; j += 2 ) printf( "%lf %lf\n", qx * j, qy * j );
}
return 0;
}
by DDDreamer @ 2021-06-26 17:45:34
显然,此样例的正确输出应该是1.0000
by yzy1 @ 2021-06-26 18:23:58
@DDDreamer 那我如果旋转不是整数度不就不会被 hack 了？
比如这样：
void Rot(double ang) {
ang = ang / 180.0L * M_PI;
for (ll i = 1; i <= n; ++i) {
double x = a[i].first, y = a[i].second;
a[i].first = x * std::cos(ang) - y * std::sin(ang);
a[i].second = y * std::cos(ang) + x * std::sin(ang);
}
}
signed main() {
std::cin >> n;
for (ll i = 1; i <= n; ++i) {
std::cin >> a[i].first >> a[i].second;
}
double minn = INF;
while (double(clock()) / CLOCKS_PER_SEC <= 0.6L) {
Rot(rand() % 36000 / 100.0);
std::sort(a + 1, a + 1 + n);
for (ll i = 1; i <= n; ++i) {
for (ll j = i + 1; j <= std::min(n, i + 5); ++j) {
double res = std::sqrt(std::pow(a[i].first - a[j].first, 2) +
std::pow(a[i].second - a[j].second, 2));
minn = std::min(minn, res);
}
}
}
std::printf("%.4lf\n", minn);
return 0;
}by yzy1 @ 2021-06-26 18:24:41
感觉这个 hack 不是很好啊
by DDDreamer @ 2021-06-26 21:31:25
@yzy1 这个样例都摆出来了解决当然很容易了.重要的是随机旋转不能完美解决这个问题,稍微修改下参数.
by OIforJoy @ 2021-06-26 22:42:33
@DDDreamer 这个应该没有办法证明随机旋转不可行的吧。。。不过他们的实现方法应该是真的有问题，我这里大概可以证明似乎你随机旋转n^(0.5+eps)次的话可以解决,但是这似乎用在原题上可能会爆？
by DDDreamer @ 2021-07-04 02:05:05
@OIforJoy 我这个数据当然写的很烂，但可以看出，精度允许范围内,布置围绕