hdu 4885 TIANKENG’s travel(bfs)

题目大意：给定N，L，表示有N个加油站，每次加满油能够移动距离L，必须走直线，可是能够为斜线。然后给出sx，sy，ex，ey，以及N个加油站的位置，问说最少经过几个加油站，路过不加油也算。

解题思路：一開始以为经过能够不算，所以o(n2)的复杂度建图，然后用bfs求最短距离，结果被FST了。

将点依照x坐标排序，这样在建图是保证当前点为最左点，每次建立一条边的时候，将该边的斜率记录，下次有同样的斜率则不加边，斜率能够用两个整数表示，可是要注意化简成最简。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <queue>

#include <vector>

#include <set>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int maxn = 1005;

struct point {

    int id;

    ll x, y;

}p[maxn], s, e;

ll L;

int N, d[maxn];

vector<int> g[maxn];

set<pii> vis;

inline ll gcd (ll a, ll b) {

    return b == 0 ? a : gcd(b, a%b);

}

inline bool cmp (const point& a, const point& b) {

    return a.x < b.x;

}

inline ll dis (ll x, ll y) {

    return x * x + y * y;

}

bool search (ll x, ll y) {

    ll d = gcd(x, y);

    if (d < 0)

        d = -d;

    x /= d; y /= d;

    if (vis.find(make_pair(x, y)) != vis.end())

        return true;

    vis.insert(make_pair(x, y));

    return false;

}

void addEdge (point a, point b) {

    ll d = dis(a.x - b.x, a.y - b.y);

    if (d <= L && !search(b.x - a.x, b.y - a.y)) {

        g[a.id].push_back(b.id);

        g[b.id].push_back(a.id);

        //printf("%d %d %lld %lld\n", a.id, b.id, d, L * L);

    }

}

void init () {

    scanf("%d%lld", &N, &L);

    scanf("%lld%lld%lld%lld", &p[0].x, &p[0].y, &p[1].x, &p[1].y);

    p[0].id = 0;

    p[1].id = 1;

    N += 2;

    L = L * L;

    for (int i = 0; i < N; i++)

        g[i].clear();

    for (int i = 2; i < N; i++) {

        scanf("%lld%lld", &p[i].x, &p[i].y);

        p[i].id = i;

    }

    sort(p, p + N, cmp);

    for (int i = 0; i < N; i++) {

        vis.clear();

        for (int j = i + 1; j < N; j++)

            addEdge(p[i], p[j]);

    }

}

void bfs () {

    queue<int> que;

    que.push(0);

    memset(d, -1, sizeof(d));

    d[0] = 0;

    while (!que.empty()) {

        int u = que.front();

        que.pop();

        if (u == 1) {

            printf("%d\n", d[u]-1);

            return;

        }

        for (int i = 0; i < g[u].size(); i++) {

            int v = g[u][i];

            if (d[v] == -1) {

                d[v] = d[u] + 1;

                que.push(v);

            }

        }

    }

    printf("impossible\n");

}

int main () {

    int cas;

    scanf("%d", &cas);

    while (cas--) {

        init();

        bfs();

    }

    return 0;

}