首页 > ACM题库 > HDU-杭电 > HDU 3767-Paintball[解题报告]HOJ
2015
04-10

HDU 3767-Paintball[解题报告]HOJ

Paintball

问题描述 :

You are playing paintball on a 1000×1000 square field. A number of your opponents are on the field hiding behind trees at various positions. Each opponent can fire a paintball a certain distance in any direction. Can you cross the field without being hit by a paintball?

Assume that the southwest corner of the field is at (0,0) and the northwest corner at (0,1000).

输入:

The input consists of a line containing n <= 1000, the number of opponents. A line follows for each opponent, containing three real numbers: the (x,y) location of the opponent and its firing range. The opponent can hit you with a paintball if you ever pass within his firing range.

You must enter the field somewhere between the southwest and northwest corner and must leave somewhere between the southeast and northeast corners.

输出:

The input consists of a line containing n <= 1000, the number of opponents. A line follows for each opponent, containing three real numbers: the (x,y) location of the opponent and its firing range. The opponent can hit you with a paintball if you ever pass within his firing range.

You must enter the field somewhere between the southwest and northwest corner and must leave somewhere between the southeast and northeast corners.

样例输入:

3
500 500 499
0 0 999
1000 1000 200

样例输出:

0.00 1000.00 1000.00 800.00

/*
 * Author: NomadThanatos
 * Created Time: 2011/3/10 18:47:54
 * File Name: E.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;
#define SZ(v) ((int)(v).size())

const int MAXINT = -1u>>1;
const int MAXN = 1000 + 50;
const double EPS = 1e-9;

int N;
bool can;
bool vis[MAXN];
double nw,ne;
double x[MAXN],y[MAXN],r[MAXN];

int sgn(const double &x) {return (int)((x > EPS) - (x < -EPS));}

void dfs(const int &i) {
 vis[i] = true;
 for(int j = 0 ; j < N ; j++) {
 if (sgn(sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j]) <= 0 && !vis[j]) dfs(j);
 }
 if (sgn(y[i] - r[i]) <= 0) can = false;
 if (sgn(x[i] - r[i]) <= 0) {
 nw = min(nw,y[i] - sqrt(r[i] * r[i] - x[i] * x[i]));
 }
 if (sgn(x[i] + r[i] - 1000) >= 0) {
 ne = min(ne,y[i] - sqrt(r[i] * r[i] - (1000.0 - x[i]) * (1000.0 - x[i])));
 }
}

int main() {
 while(scanf("%d",&N) == 1 && N) {
 ne = nw = 1000.0;
 for(int i = 0 ; i < N ; i++) {
 scanf("%lf%lf%lf",x + i,y + i,r + i);
 vis[i] = false;
 }
 can = true;
 for(int i = 0 ; i < N ; i++) {
 if (!vis[i] && sgn(y[i] + r[i] - 1000.0) >= 0) {
 dfs(i);
 }
 }
 if (can) {
 printf("0.00 %0.2lf 1000.00 %0.2lf\n",nw,ne);
 }
 else printf("IMPOSSIBLE\n");
 }
 return 0;
}

  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. [email protected]