UVa 10535 – Shooter [贪心+几何]

Link

传送门

Problem

The shooter is in a great problem. He is trapped in a “2D” maze with a laser gun and can use it once. The gun is very powerful and the laser ray, it emanates can traverse infinite distance in its direction. In the maze the targets are some walls (Here this is line segments). If the laser ray touches any wall or intersects it, that wall will be destroyed and the ray will advance ahead. The shooter wants to know the maximum number of walls, he can destroy with a single shot. The shooter will never stand on a wall.

Mean

在一个二维的坐标系中,有N堵墙,每堵墙有知道他的两端坐标。有一个抢手,他的枪可以穿透墙打翻并且可以打无限远。问你这个抢手打一枪最多能打翻几堵墙(擦过也算可以打翻)。

Analysis

这道题类似于《算法竞赛训练指南》上的例题:uva1398

  1. 为了计算方便,可以将坐标系中所有点平移,将抢手的位置化为(0, 0).
  2. 对于这些线段,可以将所有的端点排序后扫描,起点+1,终点-1,这样就可以扫描出最大经过多少堵墙。
  3. 每个点要计算出相对于x轴正向的角度,便于排序。可以使用atan2(y,x)函数计算极角。注意参数y在前x在后,计算结果范围为(-pi, pi),x轴上方为正,下方为负。
  4. 由于atan2计算出的极角不方便排序和比较,我们可以把它进一步转为为相对于x轴正向的角度。
  5. 这样就可以从x轴正向开始扫描。但是会发现有经过x轴正向的线段,可以把它切分为x轴上下方两部分。
  6. 对于点的排序,当角度相同时,根据逻辑,要先加后减,才能保证是正确答案。

这道题真的学到了不少东西,包括对atan2函数更深刻的认识以及一些小细节的处理。

Code

#include <bits/stdc++.h>
using namespace std;
using P = pair<double, double>;

const int maxn = 512;
const double pi = acos(-1), eps = 1e-7;

struct Node {
    double angle;
    int type;
    Node(double angle, int type):angle(angle), type(type) {}
    bool operator < (const Node & rhs) const {
        if(fabs(angle - rhs.angle) > eps) return angle < rhs.angle;
        return type > rhs.type;
    }
};
int n;
P st[maxn], ed[maxn];
vector<Node> po;

void init() {
    for(int i = 0; i < n; ++i) {
        cin >> st[i].first >> st[i].second >> ed[i].first >> ed[i].second;
    }
    double x, y; cin >> x >> y;
    for(int i = 0; i < n; ++i) {
        st[i].first -= x; st[i].second -= y;
        ed[i].first -= x; ed[i].second -= y;
    }
    po.clear();
    for(int i = 0; i < n; ++i) {
        double ang1 = atan2(st[i].second, st[i].first);
        double ang2 = atan2(ed[i].second, ed[i].first);
        if(ang1 < 0) ang1 = 2 * pi + ang1;
        if(ang2 < 0) ang2 = 2 * pi + ang2;
        if(ang1 > ang2) swap(ang1, ang2);
        if(ang2 - ang1 >= pi) {
            po.push_back(Node(0, 1));
            po.push_back(Node(ang1, -1));
            po.push_back(Node(ang2, 1));
            po.push_back(Node(2*pi, -1));
        } else {
            po.push_back(Node(ang1, 1));
            po.push_back(Node(ang2, -1));
        }
    }
    sort(po.begin(), po.end());
}

void solve() {
    int cnt = 0, ans = 0;
    for(auto &no : po)
        ans = max(ans, cnt += no.type);
    cout << ans << endl;
}

int main()
{
    while(cin >> n, n) {
        init();
        solve();
    }
    return 0;
}

欢迎留言