2014-07-24

UVa 11696 - Beacons

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

In ancient times, communication was not as swift as it is today. When a kingdom was at war, it could take months to muster all the armed forces. But by using fire-lit beacons at strategic locations, it was still possible to quickly send emergency signals.

When the first beacon is lit, all other beacons within sight from it are also lit. All beacons within sight of these are then lit, and so on until all beacons are lit - assuming of course that all beacons are within sight of each other, directly or indirectly. If they are not, the dire news must be carried by riders between some beacons.

Given the location of all beacons in the kingdom as well as the location and size of all mountain peaks, write a program that determines how many messages must be sent by riders in order for all beacons to be lit when an enemy threatens the country.

For simplicity, we model the country in the following way: a beacon is represented as a point in the xy-plane and a mountain peak is represented as a circle. Two beacons are considered to be within sight of each other if no mountain peak blocks the straight line between the two beacons.

The input will be constructed so that the straight line between any pair of beacons will not touch the circumference of a mountain peak, unless it passes through the interior of another mountain peak. Mountain peaks will not overlap or touch, nor will any beacon be on a mountain peak or on its circumference.

Input

The first line of the input file contains an integer N (N<25) which denotes the total number of test cases. The description of each test case is given below:

The first line of input for each test case contains two integers n (1 ≤ n ≤ 1000) and m (0 ≤ m ≤ 1000) the number of beacons and the number of mountain peaks, respectively. Then follow n lines specifying the locations of the beacons. The location of each beacon is given as a pair of integers x and y (0 ≤ x, y ≤ 10000). Then follow m lines describing the mountain peaks. Each mountain peak is given as a pair of integers x and y x(0 ≤ x, y ≤ 10000) specifying the location of the peak and a radius r (1 ≤ r ≤ 5000).

Output

For each test case the output should be a line containing a single integer: the number of messages that must be carried by riders for all beacons to be lit.

Sample Input

Sample Output

1
2

2
1

Solution

題目描述：

每個山峰將會由一個點為圓心和半徑構成，而從編號 1 將會發送狼煙，這個狼煙要傳遞到每一個其他點，但有可能會被山峰擋住 (當作圓柱也行)，因此必須採用人工的方式將訊息傳遞到另一個點進行施放，當每一個點獲得訊息後，也會點燃狼煙傳給其他點。

求最少的人工傳遞次數。

題目解法：

找到這題的 graph，接著找有多少個 component 即可，但是對於建造 graph 的成本上，不能使用 O(n n m) 任抓兩個點並且檢查是否有圓柱遮蔽。

窮舉對於每一個點，將其當作圓心，得到其他點的極角排序，接著對於每一個圓柱找到遮蔽的極角區間，二分搜索區間後，直接針對該區間的點進行圓柱遮蔽判斷。如此一來建圖的效率就能快很多。

#include <stdio.h>
#include <math.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    bool operator<(const Pt &a) const {
        if(fabs(x-a.x) > eps)	return x < a.x;
        return y < a.y;
    }
    bool operator==(const Pt &a) const {
        return fabs(x-a.x) < eps && fabs(y-a.y) < eps;
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator/(const double val) const {
        return Pt(x / val, y / val);
    }
    Pt operator*(const double val) const {
        return Pt(x * val, y * val);
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
Pt D[1024], E[1024];
double Er[1024];
#define maxL (1048576>>5)+1
#define GET(x) (g[(x)>>5]>>((x)&31)&1)
#define SET(x) (g[(x)>>5] |= 1<<((x)&31))
int g[maxL];
void buildGraph(int n, int m) {
    memset(g, 0, sizeof(g));// all link
    sort(D, D+n); // let (i, j) i < j for polar angle in [-pi/2, pi/2]
    for(int i = 0; i < n; i++) {
        vector< pair<double, int> > A;
        for(int j = i+1; j < n; j++)
            A.push_back(make_pair(atan2(D[j].y - D[i].y, D[j].x - D[i].x), j));
        sort(A.begin(), A.end());
        for(int j = 0; j < m; j++) { // test obstacle
            double mm = atan2(E[j].y - D[i].y, E[j].x - D[i].x);
            double theta = asin(Er[j] / dist(E[j], D[i])), L = mm - theta, R = mm + theta;
            int st = lower_bound(A.begin(), A.end(), make_pair(L, -1)) - A.begin();
            for(int k = st; k < A.size() && A[k].first <= R; k++) {
                if(dot(D[i] - D[A[k].second], E[j] - D[A[k].second]) > 0)
                    SET(i * n + A[k].second), SET(A[k].second * n + i);
            }
        }
    }
}
int visited[1024];
void dfs(int u, int n) {
    visited[u] = 1;
    for(int i = 0; i < n; i++) {
        if(!GET(u * n + i) && !visited[i]) {
            dfs(i, n);
        }
    }
}
int main() {
    int testcase, n, m;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++) 
            scanf("%lf %lf", &D[i].x, &D[i].y);
        for(int i = 0; i < m; i++)
            scanf("%lf %lf %lf", &E[i].x, &E[i].y, &Er[i]);
        buildGraph(n, m);
        int ret = 0;
        memset(visited, 0, sizeof(visited));
        for(int i = 0; i < n; i++) // compute how many component
            if(visited[i] == 0)
                dfs(i, n), ret++;
        printf("%d\n", ret - 1);
    }
    return 0;
}
/*
2
6 3
1 8
5 4
7 7
9 2
16 6
17 10
4 7 2
6 3 1
12 6 3
4 4
0 4
8 4
4 0
4 8
2 2 1
6 2 1
2 6 1
6 6 1
*/

Morris' Blog