267

# 题目

## Description

Osu! is a very popular music game. Basically, it is a game about clicking. Some points will appear on the screen at some time, and you have to click them at a correct time.

Now, you want to write an algorithm to estimate how diffecult a game is.

To simplify the things, in a game consisting of N points, point i will occur at time t i at place (x i, y i), and you should click it exactly at t i at (x i, y i). That means you should move your cursor from point i to point i+1. This movement is called a jump, and the difficulty of a jump is just the distance between point i and point i+1 divided by the time between t i and t i+1. And the difficulty of a game is simply the difficulty of the most difficult jump in the game.

Now, given a description of a game, please calculate its difficulty.

## Input

The first line contains an integer T (T ≤ 10), denoting the number of the test cases.

For each test case, the first line contains an integer N (2 ≤ N ≤ 1000) denoting the number of the points in the game. Then N lines follow, the i-th line consisting of 3 space-separated integers, t i(0 ≤ t i < t i+1 ≤ 10 6), x i, and y i (0 ≤ x i, y i ≤ 10 6) as mentioned above.

## Output

For each test case, output the answer in one line.

Your answer will be considered correct if and only if its absolute or relative error is less than 1e-9.

2
5
2 1 9
3 7 2
5 9 0
6 6 3
7 6 0
10
11 35 67
23 2 29
29 58 22
30 67 69
36 56 93
62 42 11
67 73 29
68 19 21
72 37 84
82 24 98

9.2195444573
54.5893762558

# 代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！

*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 1005;

struct Node {
double t,x,y;
bool operator < (const Node &rhs)const {
return t < rhs.t;
}
double operator - (const Node &rhs)const {
return sqrt((x - rhs.x)*(x - rhs.x) + (y - rhs.y)*(y-rhs.y));
}
};

Node note[maxn];

void Do() {
int n;
cin >> n;
for(int i = 0;i < n;i++)
cin >> note[i].t >> note[i].x >> note[i].y;
sort(note,note + n);

double Max = 0;
for(int i = 1;i < n;i++)
Max = max(Max,(note[i] - note[i - 1]) / (note[i].t - note[i - 1].t));

cout << fixed << setprecision(20) << Max << endl;
}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);

int T;
cin >> T;
while(T--)
Do();

return 0;
}

• 点击查看/关闭被识别为广告的评论