Lightning
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1565 Accepted Submission(s): 515
Problem Description
There are N robots standing on the ground (Don't know why. Don't know how).
Suddenly the sky turns into gray, and lightning storm comes! Unfortunately, one of the robots is stuck by the lightning!
So it becomes overladen. Once a robot becomes overladen, it will spread lightning to the near one.
The problem is: How many kind of lightning shape if all robots is overladen? The answer can be very large so we output the answer modulo 10007. If some of the robots cannot be overladen, just output -1.
Suddenly the sky turns into gray, and lightning storm comes! Unfortunately, one of the robots is stuck by the lightning!
So it becomes overladen. Once a robot becomes overladen, it will spread lightning to the near one.
The spreading happens when:
Robot A is overladen but robot B not.
The Distance between robot A and robot B is no longer than R.
No other robots stand in a line between them.
In this condition, robot B becomes overladen.
We assume that no two spreading happens at a same time and no two robots stand at a same position.
The problem is: How many kind of lightning shape if all robots is overladen? The answer can be very large so we output the answer modulo 10007. If some of the robots cannot be overladen, just output -1.
Input
There are several cases.
The first line is an integer T (T < = 20), indicate the test cases.
For each case, the first line contains integer N ( 1 < = N < = 300 ) and R ( 0 < = R < = 20000 ), indicate there stand N robots; following N lines, each contains two integers ( x, y ) ( -10000 < = x, y < = 10000 ), indicate the position of the robot.
The first line is an integer T (T < = 20), indicate the test cases.
For each case, the first line contains integer N ( 1 < = N < = 300 ) and R ( 0 < = R < = 20000 ), indicate there stand N robots; following N lines, each contains two integers ( x, y ) ( -10000 < = x, y < = 10000 ), indicate the position of the robot.
Output
One line for each case contains the answer.
Sample Input
3 3 2 -1 0 0 1 1 0 3 2 -1 0 0 0 1 0 3 1 -1 0 0 1 1 0
Sample Output
3 1 -1
Author
BUPT
Source
Recommend
生成树计数， martix-tree定理，行列式那边取模时要用逆元
/*************************************************************************
> File Name: hdu4305.cpp
> Author: ALex
> Mail: 405045132@qq.com
> Created Time: 2015年01月26日 星期一 21时31分21秒
************************************************************************/
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 330;
const int mod = 10007;
int mat[N][N];
struct node
{
int x, y;
}point[N];
int extend_gcd (int a, int b, int &x, int &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
int gcd = extend_gcd (b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * x;
}
int get_inverse (int num)
{
int x, y;
extend_gcd (num, mod, x, y);
return (x % mod + mod) % mod;
}
int Det (int n) // 求行列式的值，涉及到除法，所以要用逆元
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
mat[i][j] = (mat[i][j] % mod + mod) % mod;
}
}
int res = 1;
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
if (mat[j][i])
{
for (int k = i; k < n; ++k)
{
swap (mat[i][k], mat[j][k]);
}
if (i != j)
{
res = (-res + mod) % mod;
}
break;
}
}
if (!mat[i][i])
{
res = -1;
break;
}
for (int j = i + 1; j < n; ++j)
{
int mut = (mat[j][i] * get_inverse (mat[i][i])) % mod;
for (int k = i; k < n; ++k)
{
mat[j][k] = (mat[j][k] - (mat[i][k] * mut) % mod + mod) % mod;
}
}
res = (res * mat[i][i]) % mod;
}
return res;
}
bool is_line (int i, int j, int k)
{
int x1 = point[k].x - point[i].x;
int y1 = point[k].y - point[i].y;
int x2 = point[k].x - point[j].x;
int y2 = point[k].y - point[j].y;
return x1 * y2 - x2 * y1;
}
bool is_ok (int i, int j, int R, int n)
{
int x = point[i].x - point[j].x;
int y = point[i].y - point[j].y;
if (x * x + y * y > R * R)
{
return false;
}
for (int k = 0; k < n; ++k)
{
if (k == i || k == j)
{
continue;
}
if (point[k].x )
if (is_line(i, j, k))
{
continue;
}
if ((point[k].x - point[i].x) * (point[k].x - point[j].x) > 0)
{
continue;
}
if ((point[k].y - point[i].y) * (point[k].y - point[j].y) > 0)
{
continue;
}
return false;
}
return true;
}
int main ()
{
int t;
scanf("%d", &t);
while (t--)
{
int n, R;
scanf("%d%d", &n, &R);
for (int i = 0; i < n; ++i)
{
scanf("%d%d", &point[i].x, &point[i].y);
}
memset (mat, 0, sizeof(mat));
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (is_ok (i, j, R, n))
{
mat[i][j] = -1;
mat[j][i] = -1;
}
}
}
for (int i = 0; i < n; ++i)
{
int tmp = 0;
for (int j = 0; j < n; ++j)
{
tmp += mat[i][j];
}
mat[i][i] = -tmp;
}
int ans = Det (n - 1);
printf("%d\n", ans);
}
return 0;
}