| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98386 |
2019-02-22T19:37:56 Z |
Kastanda |
Park (BOI16_park) |
C++11 |
|
1453 ms |
48776 KB |
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef double ld;
const int N = 2019;
int n, q, W, H, X[N], Y[N], R[N], P[N];
ld D[N][N], F[5][5];
inline bool CMP(pair < int , int > a, pair < int , int > b)
{
return (D[a.first][a.second] < D[b.first][b.second]);
}
int Find(int v)
{
return (P[v] ? (P[v] = Find(P[v])) : v);
}
inline void smin(ld &a, ld b)
{
a = min(a, b);
}
int main()
{
scanf("%d%d%d%d", &n, &q, &W, &H);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &X[i], &Y[i], &R[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
ld d = sqrt((ld)(X[i] - X[j]) * (X[i] - X[j]) + (ld)(Y[i] - Y[j]) * (Y[i] - Y[j]));
d = max(d - R[i] - R[j], (ld)0.000000); d /= 2.0; D[i][j] = d;
}
for (int i = 1; i <= n; i++)
{
D[i][n + 1] = D[n + 1][i] = max((ld)Y[i] - R[i], (ld)0.0000) / 2.0;
D[i][n + 3] = D[n + 3][i] = max((ld)H - Y[i] - R[i], (ld)0.0000) / 2.0;
D[i][n + 2] = D[n + 2][i] = max((ld)W - X[i] - R[i], (ld)0.0000) / 2.0;
D[i][n + 4] = D[n + 4][i] = max((ld)X[i] - R[i], (ld)0.0000) / 2.0;
}
D[n + 1][n + 3] = D[n + 3][n + 1] = H / 2.0;
D[n + 2][n + 4] = D[n + 4][n + 2] = W / 2.0;
for (int i = 0; i <= 4; i++)
for (int j = 0; j <= 4; j++)
F[i][j] = 1e10;
vector < pair < int , int > > E;
for (int i = 1; i <= n + 4; i++)
for (int j = i + 1; j <= n + 4; j++)
if (i <= n || j <= n)
E.pb({i, j});
E.pb({n + 1, n + 3});
E.pb({n + 2, n + 4});
sort(E.begin(), E.end(), CMP);
for (auto edge : E)
{
int v = edge.first, u = edge.second;
ld d = D[v][u];
v = Find(v);
u = Find(u);
if (v != u)
P[v] = u;
if (Find(n + 1) == Find(n + 3))
{
smin(F[1][2], d);
smin(F[1][3], d);
smin(F[2][4], d);
smin(F[3][4], d);
}
if (Find(n + 2) == Find(n + 4))
{
smin(F[1][3], d);
smin(F[1][4], d);
smin(F[2][3], d);
smin(F[2][4], d);
}
for (int i = 1; i <= 4; i++)
{
int a = n + i;
int b = (i > 1) ? (a - 1) : (n + 4);
if (Find(a) == Find(b))
for (int j = 1; j <= 4; j++)
if (i != j)
smin(F[i][j], d), smin(F[j][i], d);
}
}
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
smin(F[i][j], F[j][i]);
for (; q; q --)
{
int r, e;
scanf("%d%d", &r, &e);
for (int j = 1; j <= 4; j++)
if (r <= F[e][j])
printf("%d", j);
printf("\n");
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &q, &W, &H);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &X[i], &Y[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &r, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1265 ms |
48776 KB |
Output is correct |
| 2 |
Correct |
1453 ms |
48600 KB |
Output is correct |
| 3 |
Correct |
1435 ms |
48576 KB |
Output is correct |
| 4 |
Correct |
1436 ms |
48600 KB |
Output is correct |
| 5 |
Correct |
1395 ms |
48604 KB |
Output is correct |
| 6 |
Correct |
1339 ms |
48604 KB |
Output is correct |
| 7 |
Correct |
780 ms |
48604 KB |
Output is correct |
| 8 |
Correct |
681 ms |
48608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
2104 KB |
Output is correct |
| 2 |
Correct |
63 ms |
2072 KB |
Output is correct |
| 3 |
Correct |
54 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
54 ms |
2164 KB |
Output is correct |
| 5 |
Correct |
58 ms |
2164 KB |
Output is correct |
| 6 |
Correct |
62 ms |
2164 KB |
Output is correct |
| 7 |
Incorrect |
49 ms |
760 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1265 ms |
48776 KB |
Output is correct |
| 2 |
Correct |
1453 ms |
48600 KB |
Output is correct |
| 3 |
Correct |
1435 ms |
48576 KB |
Output is correct |
| 4 |
Correct |
1436 ms |
48600 KB |
Output is correct |
| 5 |
Correct |
1395 ms |
48604 KB |
Output is correct |
| 6 |
Correct |
1339 ms |
48604 KB |
Output is correct |
| 7 |
Correct |
780 ms |
48604 KB |
Output is correct |
| 8 |
Correct |
681 ms |
48608 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
