Submission #1053845
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
int n;
vi x, y, c;
bool possible(double time) {
double xl, xh, yl, yh;
double dist = time / c[0];
xl = x[0] - dist;
xh = x[0] + dist;
yl = y[0] - dist;
yh = y[0] + dist;
double nxl, nxh, nyl, nyh;
FOR (i, 1, n) {
dist = time / c[i];
nxl = x[i] - dist;
nxh = x[i] + dist;
nyl = y[i] - dist;
nyh = y[i] + dist;
if (nxh < xl || xh < nxl || nyh < yl || yh < nyl) {
return false;
}
xl = max(xl, nxl);
xh = min(xh, nxh);
yl = max(yl, nyl);
yh = min(yh, nyh);
}
return true;
}
int main() {
scanf("%d", &n);
x.resize(n);
y.resize(n);
c.resize(n);
rep (i, n) {
scanf("%d %d %d", &x[i], &y[i], &c[i]);
}
double h = 2.0 * 1e12;
double l = 0.0;
double mid;
while (h - l > 1e-6) {
mid = (h + l) / 2;
if (possible(mid)) {
h = mid;
} else {
l = mid;
}
}
printf("%.9f\n", h);
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 高橋ノルム君 |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
100 |
Code Size |
1855 Byte |
Status |
AC |
Exec Time |
12 ms |
Memory |
760 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
AC
|
|
|
Set Name |
Test Cases |
Sample |
|
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt |
Subtask2 |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
12 ms |
760 KB |
subtask0_sample_02.txt |
AC |
2 ms |
256 KB |
subtask0_sample_03.txt |
AC |
3 ms |
256 KB |
subtask0_sample_04.txt |
AC |
3 ms |
256 KB |
subtask1_01.txt |
AC |
3 ms |
256 KB |
subtask1_02.txt |
AC |
3 ms |
256 KB |
subtask1_03.txt |
AC |
3 ms |
256 KB |
subtask1_04.txt |
AC |
3 ms |
256 KB |
subtask1_05.txt |
AC |
3 ms |
256 KB |
subtask1_06.txt |
AC |
3 ms |
256 KB |
subtask1_07.txt |
AC |
3 ms |
256 KB |
subtask1_08.txt |
AC |
3 ms |
256 KB |
subtask1_09.txt |
AC |
3 ms |
256 KB |
subtask1_10.txt |
AC |
3 ms |
256 KB |
subtask1_11.txt |
AC |
3 ms |
256 KB |
subtask1_12.txt |
AC |
3 ms |
256 KB |
subtask1_13.txt |
AC |
3 ms |
256 KB |
subtask2_01.txt |
AC |
3 ms |
256 KB |
subtask2_02.txt |
AC |
3 ms |
256 KB |
subtask2_03.txt |
AC |
3 ms |
256 KB |
subtask2_04.txt |
AC |
3 ms |
256 KB |
subtask2_05.txt |
AC |
4 ms |
256 KB |
subtask2_06.txt |
AC |
4 ms |
256 KB |
subtask2_07.txt |
AC |
3 ms |
256 KB |
subtask2_08.txt |
AC |
4 ms |
256 KB |
subtask2_09.txt |
AC |
4 ms |
256 KB |
subtask2_10.txt |
AC |
3 ms |
256 KB |
subtask2_11.txt |
AC |
4 ms |
256 KB |
subtask2_12.txt |
AC |
3 ms |
256 KB |
subtask2_13.txt |
AC |
4 ms |
256 KB |