POJ3347 - Kadj Squares

题意

给出指定变长的正方形，按输入顺序，将这些正方形以$45°$倾斜角，某一顶点在$x$轴，且后放的正方形与$x$轴相交的顶点的横坐标要大于前放的正方形的限制下依次放置。

问最后由上往下看，能看到多少正方形，其编号是？

思路

一个朴素的想法就是求出所有的正方形的坐标，然后就可以转化为一个类似线段覆盖（将如此放置的正方形的左端点当成线段左端点，对正方形的右端点同理）的问题。

而后，对这些线段的纵坐标从大到小进行排序。若某一线段可以从上往下看到，那么它不会被排序后位于它之前的线段所覆盖，$O(n^2)$进行枚举即可。

蠢方法

为了便于表述，先定义：

边$L$：正方形中，$x$轴相接的顶点和正方形的右端点所连接组成的线段；

边$T$​：正方形中，纵坐标最大的点，即上端点，和正方形的右端点所连接组成的线段；

垂线段：正方形的上顶点和下顶点相连接得到的线段

我最初的做法是先求出所有正方形与$x$轴相接的点的坐标，具体过程如下：

1. 首先确定第一个点，设长度数组为$Len$，容易得到第一个点的坐标为$(\frac{Len[1]}{\sqrt{2}}, 0)$​

2. 确定下一个正方形$S$与先前的某一正方形$S’$是如何相接的，有三种情况：

   ① $S$与$S’$的边$L$相接；设$S’$的右端点为$P$，若$P.y - \frac{S.Len}{\sqrt{2}} \geq 0$，则为该种情况；

   ② $S$与$S’$的边$T$相接；将边$T$延长，得到与$x$轴的交点$G$，而后得到正方形$S$的左端点$G’=(G.x - \frac{S.len}{\sqrt{2}}, G.y+\frac{S.len}{\sqrt{2}})$，若线段$GG’$与先前所有正方形的垂线段都不规范相交，则为该种情况；

   ③ $S$的左端点直接贴在$y$轴上，不与任何一个先前的正方形有相交之处；若前两种情况均不满足，则为该种情况。

3. 依次求出所有正方形与$x$轴相接点的坐标，存入数组中。

由此即可得到所有正方形的坐标，容易进一步推导得到正方形的左右端点，即转化为线段覆盖问题。

代码：

// 3347.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>

#define maxn 100005
using namespace std;
int n;
double l[maxn];
const double eps = 1e-8;

int sgn(double x) {
    if (fabs(x) < eps)
        return 0;

    return x > 0 ? 1 : -1;
}

double sqrtV(double len) {
    return len / sqrt(2.0);
}

struct Point {
    int id;
    double x, y;

    Point() {}

    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }

    Point(double _x, double _y, int _id) {
        x = _x;
        y = _y;
        id = _id;
    }

    Point(Point _p, int _id) {
        x = _p.x;
        y = _p.y;
        id = _id;
    }

    bool operator<(const Point &A) {
        return sgn(x - A.x) == 0 ? y < A.y : x < A.x;
    }

    bool operator==(const Point &A) {
        return sgn(x - A.x) == 0 && sgn(y - A.y) == 0;
    }

    double operator^(const Point &A) {
        return x * A.y - y * A.x;
    }

    double operator*(const Point &A) {
        return x * A.x + y * A.y;
    }

    Point operator-(const Point &A) {
        return Point(x - A.x, y - A.y);
    }

    void print() {
        printf("[Point] x:%.2lf, y:%.2lf id:%d\n", x, y, id);
    }
};

//ty = 1: top to mid, ty = 0: mid to low
struct Line {
    int id, ty;
    Point s, e;

    Line() {}

    Line(Point _s, Point _e) {
        s = _s;
        e = _e;
    }

    Line(Point _s, Point _e, int _id, int _ty) {
        s = _s;
        e = _e;
        id = _id;
        ty = _ty;
    }

    // 2 -> specification intersect
    int segcrossseg(Line v) {
        int d1 = sgn((e - s) ^ (v.s - s));
        int d2 = sgn((e - s) ^ (v.e - s));
        int d3 = sgn((v.e - v.s) ^ (s - v.s));
        int d4 = sgn((v.e - v.s) ^ (e - v.s));

        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)
            return 2;

        return (d1 == 0 && sgn((v.s - s) * (v.s - e)) <= 0) ||
               (d2 == 0 && sgn((v.e - s) * (v.e - e)) <= 0) ||
               (d3 == 0 && sgn((s - v.s) * (s - v.e)) <= 0) ||
               (d4 == 0 && sgn((e - v.s) * (e - v.e)) <= 0);
    }
};

struct Segment {
    int id;
    double y;
    double lf, rt;
} SM[maxn];

bool cmp(const Segment &A, const Segment &B) {
    return A.y > B.y;
}

vector<Point> Si;
//mid point
Point calc_m(Point s, double len) {
    double mv = sqrtV(len);
    return Point(s.x + mv, s.y + mv);
}

//top point
Point calc_t(Point s, double len) {
    double mv = sqrtV(len) * 2;
    return Point(s.x, s.y + mv);
}

bool check(Point s, double len) {
    Line newV = Line(s, Point(s.x - sqrtV(len), s.y + sqrtV(len)));

    for (int i = 0; i < Si.size(); i++) {
        Point low = Si[i], up = Point(Si[i].x, 2 * sqrtV(l[Si[i].id]));

        if (newV.segcrossseg(Line(low, up)) == 2)
            return false;
    }

    return true;
}

int main(void) {
    while (cin >> n && n) {
        Si.clear();

        for (int i = 1; i <= n; i++)
            cin >> l[i];

        double init_x = sqrtV(l[1]), init_y = 0;
        //MUST Line(top, mid) or Line(mid, low)
        Si.push_back(Point(init_x, init_y, 1));
        int now = 2;

        while (now <= n) {
            int flag = 0, nsi = now - 1;

            while (!flag && nsi > 0) {
                nsi--;
                Point nowSi = Si[nsi];
                double nowLen = l[nsi + 1];

                //edge: mid to low
                if (sgn(calc_m(nowSi, nowLen).y - sqrtV(l[now])) >= 0) {
                    Point bas = calc_m(nowSi, nowLen);
                    Point ret = Point(bas.x + sqrtV(l[now]), bas.y - sqrtV(l[now]));
                    double delta = ret.y;
                    Si.push_back(Point(ret.x - delta, ret.y - delta, now));
                    now++;
                    flag = 1;
                }
                //edge: top to mid
                else if (check(Point(nowSi.x + 2 * sqrtV(nowLen), 0), l[now])) {
                    Point bas = nowSi;
                    double rl = sqrtV(nowLen);
                    Si.push_back(Point(bas.x + 2 * rl, 0, now));
                    now++;
                    flag = 1;
                }
            }

            //single
            if (!flag) {
                Si.push_back(Point(sqrtV(l[now]), 0, now));
                now++;
            }
        }

        for (int i = 0; i < n; i++) {
            SM[i].lf = Si[i].x - sqrtV(l[Si[i].id]);
            SM[i].rt = Si[i].x + sqrtV(l[Si[i].id]);
            SM[i].y = l[Si[i].id];
            SM[i].id = Si[i].id;
        }

        sort(SM, SM + n, cmp);
        vector<int> ans;
        double maxr = -1e9;

        for (int i = 0; i < n; i++) {
            double nlf = SM[i].lf, nrt = SM[i].rt;

            for (int j = 0; j < i; j++) {
                if (sgn(SM[j].y - SM[i].y) > 0) {
                    if (nlf >= SM[j].lf)
                        nlf = max(nlf, SM[j].rt);

                    if (nrt <= SM[j].rt)
                        nrt = min(nrt, SM[j].lf);
                }
            }

            //cout << nlf << " " << nrt << endl;
            if (sgn(nrt - nlf) > 0) {
                ans.push_back(SM[i].id);
            }
        }

        sort(ans.begin(), ans.end());

        for (int i = 0; i < ans.size(); i++)
            cout << ans[i] << " ";

        cout << '\n';
    }

    return 0;
}

---

更优的思路

我们不需要求出正方形的下端点坐标，只需要左端点和右端点的坐标就可以转化问题了。

而求解左端点的坐标，可以使用一些技巧推导。

• 初始时，正方形$S$的左端点坐标设为$0$，因为正方形只能放置在第一象限。

• 若正方形$S$​​贴在正方形$S’$​​边上的话，则有：

  $S.lf.x = max(S.lf.x, S’.rt.x-|S.len-S’.len|)$​​​

  这里是放大了原来的正方形，规避了小数，且不会影响最后的结果。

• 遍历所有已经求出的正方形，由于正方形间不能重叠且正方形底部端点的$x$​坐标的值严格单调递增，因此选择$S.lf.x$​中最大的一个。

最后，可以通过比较左右端点坐标求出哪些会被覆盖（代码见：CSDN - POJ3347 Kadj Squares），也可以在处理的时候顺便处理纵坐标，对其排序便于求解覆盖关系。

推导左端点的示意图如下：

使用这种求解方法可以大大减小码量。

测试数据（仅供参考）

Input

4
3 5 1 4
3
2 1 2
3
2 2 1
4
3 3 3 3
5
1 3 9 3 1
9
6 1 2 1 1 3 5 1 1
5
4 1 3 5 2
5
4 3 1 7 5
11
5 3 3 1 4 1 1 4 2 8 2
15
4 3 15 6 10 9 15 5 1 10 10 14 5 10 8
20
21 21 4 25 22 1 7 23 26 9 9 17 16 27 1 19 10 20 10 2
50
5 18 4 19 7 23 7 18 12 22 3 17 30 7 2 19 10 1 23 24 14 2 2 28 23 6 7 22 21 8 2 17 25 5 6 23 19 4 2 30 17 4 8 8 2 1 26 11 18 3
36
23 25 9 29 8 24 15 1 21 18 28 30 12 13 24 16 21 1 28 5 24 7 7 19 20 29 30 5 2 9 16 25 4 24 15 5
21
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20
18
2 5 7 4 3 20 3 4 6 1 3 25 6 7 8 10 2 1
0

Output

1 2 4 
1 3 
1 2 3 
1 2 3 4 
3 
1 4 6 7 
1 3 4 5 
1 2 4 5 
1 2 3 5 8 10 
1 3 5 6 7 10 11 12 14 15 
1 2 4 5 8 9 10 11 12 13 14 16 17 18 19 
2 4 6 8 9 10 12 13 16 19 20 21 24 25 28 29 32 33 36 37 40 41 43 47 49 
1 2 4 6 7 9 10 11 12 13 14 15 16 17 19 21 24 25 26 27 31 32 34 35 
1 2 3 4 5 6 7 8 9 10 11 21 
1 2 3 6 12 14 15 16