SPJ 已上传

非常莫名其妙的题目，以至于我怀疑题意的真实性（题面上有好几个“原文如此”，包括“原来这里有张图片”，所以题面大概是用户回忆的？）

按照现在这个题意，似乎输出

n

个长度为

x/n

，宽度为

y

，高度为

z

的长方体就是合法的。我没看到任何明确的限制能够否决这种构造，因此我十分怀疑传抄过程中某些重要的条件丢失了。否则，放在省选里过于奇怪。

原题

10^{-16}

的精度限制过于离谱，因为 std 跑出来的输出文件都达不到这个精度要求（也可能是 testlib 达不到，因为 testlib 没有显式地支持输入 long double 浮点数）。所以放宽到了

10^{-9}

。

没搞懂为啥 tag 上有网络流，先去了。

SPJ 代码：

CPP

#include "testlib.h"

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000 + 3;

long double X1[MAXN], Y1[MAXN], Z1[MAXN];
long double X2[MAXN], Y2[MAXN], Z2[MAXN];

const long double EPS = 1e-9L;

// 检查两个区间是否相交
bool check_interval_intersect(
    long double l1, long double r1,
    long double l2, long double r2
){
    return max(r1, r2) - min(l1, l2) + EPS < r1 - l1 + r2 - l2;
}

// 检查两个长方形是否相交
bool check_rectangle_intersect(
    long double p1x, long double p1y, long double p2x, long double p2y,
    long double q1x, long double q1y, long double q2x, long double q2y
    ){
    const bool &f1 = check_interval_intersect(p1x, p2x, q1x, q2x);
    const bool &f2 = check_interval_intersect(p1y, p2y, q1y, q2y);
    return f1 && f2;
}

int main(int argc, char *argv[]){
    registerTestlibCmd(argc, argv);

    int x = inf.readInt();
    int y = inf.readInt();
    int z = inf.readInt();
    int n = inf.readInt();
    
    long double x0 = 0;
    long double y0 = 0;
    long double z0 = 0;
    long double size0 = 1.0 * x * y * z / n;
    for(int i = 1;i <= n;++ i){
        
        X1[i] = ouf.readDouble(0, x, "x1");
        Y1[i] = ouf.readDouble(0, y, "y1");
        Z1[i] = ouf.readDouble(0, z, "z1");
        X2[i] = ouf.readDouble(0, x, "x2");
        Y2[i] = ouf.readDouble(0, y, "y2");
        Z2[i] = ouf.readDouble(0, z, "z2");
        
        if(X1[i] > X2[i])
            swap(X1[i], X2[i]);
        if(Y1[i] > Y2[i])
            swap(Y1[i], Y2[i]);
        if(Z1[i] > Z2[i])
            swap(Z1[i], Z2[i]);

        long double dx = X2[i] - X1[i];
        long double dy = Y2[i] - Y1[i];
        long double dz = Z2[i] - Z1[i];
        
        if(dy < dx) swap(dx, dy);
        if(dz < dx) swap(dx, dz);
        if(dz < dy) swap(dy, dz);

        long double w1 = (dx + EPS) * (dy + EPS) * (dz + EPS);
        long double w2 = (dx - EPS) * (dy - EPS) * (dz - EPS);

        if(dx < EPS || dy < EPS || dz < EPS)
            w2 = 0;

        if(!(w2 <= size0 && size0 <= w1))
            quitf(_wa, "the cake is not evenly divided.");
        
        if(i == 1){
            x0 = dx, y0 = dy, z0 = dz;
        } else {
            if(fabsl(x0 - dx) > EPS)
                quitf(_wa, "there exists two cuboids with different shape.");
            if(fabsl(y0 - dy) > EPS)
                quitf(_wa, "there exists two cuboids with different shape.");
            if(fabsl(z0 - dz) > EPS)
                quitf(_wa, "there exists two cuboids with different shape.");
        }
    }
    
    for(int i = 1;i <= n;++ i){
        for(int j = i + 1;j <= n;++ j){
            const bool &f1 = check_rectangle_intersect(
                X1[i], Y1[i], X2[i], Y2[i],
                X1[j], Y1[j], X2[j], Y2[j]
                );
            const bool &f2 = check_rectangle_intersect(
                X1[i], Z1[i], X2[i], Z2[i],
                X1[j], Z1[j], X2[j], Z2[j]
                );
            const bool &f3 = check_rectangle_intersect(
                Y1[i], Z1[i], Y2[i], Z2[i],
                Y1[j], Z1[j], Y2[j], Z2[j]
                );
            if(f1 && f2 && f3){
                quitf(_wa, "two cuboids intersect!");
            }
        }
    }
    
    quitf(_ok, "good job!");
    return 0;
}

一个可以通过本题的弱智构造：

CPP

#include<bits/stdc++.h>
#define up(l, r, i) for(int i = l, END##i = r;i <= END##i;++ i)
#define dn(r, l, i) for(int i = r, END##i = l;i >= END##i;-- i)
using namespace std;
typedef long long i64;
const int INF = 2147483647;
int qread(){
    int w = 1, c, ret;
    while((c = getchar()) >  '9' || c <  '0') w = (c == '-' ? -1 : 1); ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + c - '0';
    return ret * w;
}

int main(){
    int x = qread(), y = qread(), z = qread();
    int n = qread();
    for(int i = 1;i <= n;++ i){
        long double x1 = 1.0L * x / n * (i - 1);
        long double y1 = 0;
        long double z1 = 0;
        long double x2 = 1.0L * x / n * i;
        long double y2 = y;
        long double z2 = z;

        printf("%.20Lf %.20Lf %.20Lf ", x1, y1, z1);
        printf("%.20Lf %.20Lf %.20Lf\n", x2, y2, z2);
    }
    return 0;
}

讨论操作

回复

相关推荐

SPJ 已上传