T30204 偷上网

Garen · 2018-05-26 23:31:32 · 题解

洛谷5月月赛的T2。让我大开眼界！

Drench大佬这么说的：

B. 偷上网

如果 n = 1，则枚举一下四个角，如果都不可行，一定无解，否则就找到了合法点。

如果 n \geq 2 ，则圆的总面积一定小于正方形的面积，每次随机一个点，判断是否可行。显然随机次数不会太多就会找到合法解。

所以有一种几乎不会被hack的算法，叫做随机算法！！！

如何取随机数？

只需要include进cstdlib，srand一个种子之后，就可以用rand()取随机数啦！

随机算法的优点是随机！我设计这种算法，即使运算100000次也根本不会超时，发现100000次还WA了一个点，直接再添一个0就可以了，并不会慢太多。时限很轻松。

srand的种子要取什么？

随缘！比如19260817、你自己的手机号、你基友的生日等等都可以。

这么多种子随便取，导致出题人都没办法hack你！

代码：

#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn = 15;
double x[maxn], y[maxn];
double n, l;
int main()
{
    srand(19260817);
    scanf("%lf%lf", &n, &l);
    for(int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
    for(int i = 1; i <= 1000000; i++)
    {
        double tx = rand(), ty = rand();
        while(tx > l) tx /= 10;
        while(ty > l) ty /= 10;
        bool ok = true;
        for(int j = 1; j <= n; j++)
        {
            if(pow(tx - x[j], 2) + pow(ty - y[j], 2) < pow(l / n, 2))
            {
                ok = false;
                break;
            }
        }
        if(ok)
        {
            printf("%.3lf %.3lf\n", tx, ty);
            return 0;
        }
    }
    printf("GG\n");
    return 0;
}