2015
04-16

# Fruit Ninja

Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy, splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.
— wikipedia

It is a very popular game on cell phones where people can enjoy cutting the fruit by touching the screen. The screen is rectangular, and all the fruit can be considered as circles, with coordinate of the center, and radius. Note that the fruit may overlap with each other. In this problem, a touch is a straight line cutting through the whole screen, scoring all the fruits it cuts or touches.
Now Fred is playing the Fruit Ninja, and seems absorbed in the game. He’s desperate to create a new record, so he asks you for help. Now you are given a screen shot of the game, help him find the highest score he can get in a single touch.

The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 1000), indicating the number of fruit.
The following N lines each contains three integers Xi,Yi,Ri(-1000 <= X,Y <= 1000,1 <= Ri <= 1000), representing a fruit on the screen, where (X,Y ) is the coordinate of the center of the fruit, and Ri is the radius.
You can assume the screen is infinite.

The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains an integer N(1 <= N <= 1000), indicating the number of fruit.
The following N lines each contains three integers Xi,Yi,Ri(-1000 <= X,Y <= 1000,1 <= Ri <= 1000), representing a fruit on the screen, where (X,Y ) is the coordinate of the center of the fruit, and Ri is the radius.
You can assume the screen is infinite.

2
4
-2 5 1
5 5 1
-3 2 1
0 1 1
4
-4 5 1
3 2 1
-5 3 1
4 -3 1

Case #1: 3
Case #2: 2

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

#define forn(i, n) for(int i = 0; i < (int)(n); i++)
#define clr(a, b) memset(a, b, sizeof(a))
#define SZ(a) ((int)a.size())
#define MP make_pair
#define PB push_back
#define inf 0x3f3f3f3f
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

namespace acm {

#ifdef CHEN_PC
#define P "%lld"
#else
#define P "%I64d"
#endif

#define sqr(x) ((x)*(x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1010;
int n;

int dcmp(double x) {
if (x < -eps) return -1;
else return x > eps;
}

struct circle {
double x, y, r;
void get() {
scanf("%lf%lf%lf", &x, &y, &r);
}
};
circle cir[N];

struct node {
double angle;
int flag;
node(){}
node(double a, int f): angle(a), flag(f) {}
bool operator < (const node& u) const {
if (dcmp(angle - u.angle))
return angle < u.angle;
return flag > u.flag;
}
};
node v[20000];
int cnt;

double dis(circle u, circle v) {
return sqrt(sqr(u.x - v.x) + sqr(u.y - v.y));
}

void add(double ang1, double ang2) {
//    printf("(%g, %g)\n", ang1, ang2);
while (ang1 < -pi) ang1 += pi * 2;
while (ang1 > pi) ang1 -= pi * 2;
while (ang2 < -pi) ang2 += pi * 2;
while (ang2 > pi) ang2 -= pi * 2;
if (dcmp(ang1 - ang2) <= 0) {
v[cnt++] = node(ang1, 1);
v[cnt++] = node(ang2, -1);
} else {
v[cnt++] = node(ang1, 1);
v[cnt++] = node(pi, -1);
v[cnt++] = node(-pi, 1);
v[cnt++] = node(ang2, -1);
}
}

void solve() {
scanf("%d", &n);
//    puts("");
forn (i, n) cir[i].get();
int ans = 0;
forn (i, n) {
int tmp = 1;
cnt = 0;
forn (j, n) {
if (i == j) continue;
double d = dis(cir[i], cir[j]);
if (dcmp(cir[i].r - cir[j].r - d) > 0) continue;
if (dcmp(cir[j].r - cir[i].r - d) >= 0) {
tmp++;
continue;
}
double ang = atan2(cir[j].y - cir[i].y, cir[j].x - cir[i].x);
if (dcmp(cir[i].r + cir[j].r - d) >= 0) {
double delta = asin((cir[j].r - cir[i].r) / d);
add(ang - delta, ang + delta + pi);
} else {
double ang1, ang2;
//                printf("\n %g %g %g\n", ang, asin((cir[j].r - cir[i].r) / d),
//                        asin((cir[j].r + cir[i].r) / d));
ang1 = ang - asin((cir[j].r - cir[i].r) / d);
ang2 = ang + asin((cir[j].r + cir[i].r) / d);
ang1 = ang - asin((cir[j].r + cir[i].r) / d) + pi;
ang2 = ang + asin((cir[j].r - cir[i].r) / d) + pi;
}
}
sort(v, v + cnt);
//        puts("");
ans = max(ans, tmp);
forn (j, cnt) {
//            printf("%g, %d\n", v[j].angle, v[j].flag);
tmp += v[j].flag;
ans = max(ans, tmp);
}
//        printf("%d %d\n", i, ans);
}
printf("%d\n", ans);
}

void icpc() {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; ++i) {
printf("Case #%d: ", i);
solve();
}
}

}

int main() {
#ifdef CHEN_PC
freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
#endif
acm::icpc();
return 0;
}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯