Skip to content

L3-012 水果忍者

Statement

Metadata

  • 作者: 邓俊辉、罗必成
  • 单位: 清华大学
  • 代码长度限制: 16 KB
  • 时间限制: 250 ms
  • 内存限制: 64 MB

2010年风靡全球的“水果忍者”游戏，想必大家肯定都玩过吧？（没玩过也没关系啦~）在游戏当中，画面里会随机地弹射出一系列的水果与炸弹，玩家尽可能砍掉所有的水果而避免砍中炸弹，就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果，则会有额外的奖励，如图1所示。

图 1

现在假如你是“水果忍者”游戏的玩家，你要做的一件事情就是，将画面当中的水果一刀砍下。这个问题看上去有些复杂，让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线，使之可以穿过所有代表水果的线段。

图 2

如图2所示，其中绿色的垂直线段表示的就是一个一个的水果；灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出，对于这样一组线段的排列，我们是可以找到一刀切开所有水果的方案的。

另外，我们约定，如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者，你要如何来找到一条穿过它们的直线呢？

输入格式

输入在第一行给出一个正整数N（\le 10^4），表示水果的个数。随后N行，每行给出三个整数x、y_1、y_2，其间以空格分隔，表示一条端点为(x, y_1)和(x, y_2)的水果，其中y_1 > y_2。注意：给出的水果输入集合一定存在一条可以将其全部穿过的直线，不需考虑不存在的情况。坐标为区间 [-10^6, 10^6) 内的整数。

输出格式

在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p_1(x_1, y_1)和p_2(x_2, y_2)，格式为 x_1\quad y_1\quad x_2\quad y_2。注意：本题答案不唯一，由特殊裁判程序判定，但一定存在四个坐标全是整数的解。

输入样例 

5
-30 -52 -84
38 22 -49
-99 -22 -99
48 59 -18
-36 -50 -72

输出样例 

-99 -99 -30 -52

Solution

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

#define db double
#define ll long long
#define N 10010
const db eps = 1e-8;
map<int, int> u, d;
vector<int> p;
int n, lx, ly, rx, ry;
int used[N];
int sta[2][N], top[2];

bool Cu(int x1, int y1, int x2, int y2) {
    return 1ll * x1 * y2 < 1ll * x2 * y1;
}
bool Cd(int x1, int y1, int x2, int y2) {
    return 1ll * x1 * y2 > 1ll * x2 * y1;
}
db Y(db k, int x, int x2, int y2) {
    return k * (x - x2) + y2;
}

bool ok() {
    if (rx - lx == 0)
        return 0;
    db k = (ry - ly) * 1.0 / (rx - lx);
    for (int i = 0, len = p.size(); i < len; ++i) {
        int x = p[i];
        db y = Y(k, x, rx, ry);
        if (y > u[x] || y < d[x])
            return 0;
    }
    return 1;
}

void solve() {
    for (int i = 2; i <= top[0]; ++i) {
        lx = sta[0][i - 1], ly = u[lx];
        rx = sta[0][i], ry = u[rx];
        if (ok())
            return;
    }
    for (int i = 2; i <= top[1]; ++i) {
        lx = sta[1][i - 1], ly = d[lx];
        rx = sta[1][i], ry = d[rx];
        if (ok())
            return;
    }
}

int main() {
    while (scanf("%d", &n) != EOF) {
        p.clear();
        memset(used, 0, sizeof used);
        for (int i = 1, x, y1, y2; i <= n; ++i) {
            scanf("%d%d%d", &x, &y1, &y2);
            if (u.find(x) != u.end()) {
                u[x] = min(u[x], y1);
                d[x] = max(d[x], y2);
            } else {
                p.push_back(x);
                u[x] = y1;
                d[x] = y2;
            }
        }
        if (p.size() == 1) {
            lx = p[0];
            ly = u[p[0]];
            rx = p[0];
            ry = d[p[0]];
        } else {
            sort(p.begin(), p.end());
            top[0] = top[1] = 0;
            for (int i = 0, len = p.size(); i < len; ++i) {
                int x1, x2, x3 = p[i];
                while (top[0] >= 2) {
                    x1 = sta[0][top[0] - 1], x2 = sta[0][top[0]];
                    if (Cu(x2 - x1, u[x2] - u[x1], x3 - x2, u[x3] - u[x2]))
                        --top[0];
                    else
                        break;
                }
                sta[0][++top[0]] = x3;
                while (top[1] >= 2) {
                    x1 = sta[1][top[1] - 1], x2 = sta[1][top[1]];
                    if (Cd(x2 - x1, d[x2] - d[x1], x3 - x2, d[x3] - d[x2]))
                        --top[1];
                    else
                        break;
                }
                sta[1][++top[1]] = x3;
                // printf("%d %d\n", sta[0][top[0]], sta[1][top[1]]);
            }
            solve();
        }
        printf("%d %d %d %d\n", lx, ly, rx, ry);
    }
    return 0;
}
Last update: May 4, 2022
Back to top