| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 218674 |
2020-04-02T13:44:05 Z |
Ruxandra985 |
Park (BOI16_park) |
C++14 |
|
1977 ms |
2040 KB |
#include <bits/stdc++.h>
#define DIMN 100010
using namespace std;
deque <int> dq;
struct idk{
int x , y , r;
} c[DIMN];
int val[5][5];
int dist[DIMN];
int n , w , h;
double distt (idk x , idk y){
return sqrt ( (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y) );
}
void solve (int nod , int raza){
int i;
memset (dist , 0 , sizeof(dist));
dq.push_back(nod);
dist[nod] = 1;
while (!dq.empty()){
nod = dq.front();
dq.pop_front();
for (i = 1 ; i <= n ; i++){
if (dist[i])
continue;
if (nod <= n && distt(c[nod] , c[i]) < c[i].r + c[nod].r + 2 * raza){
dist[i] = 1;
dq.push_back(i);
}
else if (nod == n + 1 && c[i].y < c[i].r + 2 * raza) {
dist[i] = 1;
dq.push_back(i);
}
else if (nod == n + 2 && (w - c[i].x) < c[i].r + 2 * raza){
dist[i] = 1;
dq.push_back(i);
}
else if (nod == n + 3 && (h - c[i].y) < c[i].r + 2 * raza){
dist[i] = 1;
dq.push_back(i);
}
else if (nod == n + 4 && c[i].x < c[i].r + 2 * raza){
dist[i] = 1;
dq.push_back(i);
}
}
if (nod <= n){
i = nod;
if (c[i].y < c[i].r + 2 * raza) {
dist[n + 1] = 1;
}
if ((w - c[i].x) < c[i].r + 2 * raza){
dist[n + 2] = 1;
}
if ((h - c[i].y) < c[i].r + 2 * raza){
dist[n + 3] = 1;
}
if (c[i].x < c[i].r + 2 * raza){
dist[n + 4] = 1;
}
}
}
}
int connect (int i , int j , int raza){
/// cu raza, liniile i si j se conecteaza?
//if (i == 1 && j == 2)
// printf ("a");
solve(n + i , raza);
return dist[n + j];
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int i , m , j , st , dr , mid , en , r;
fscanf (fin,"%d%d%d%d",&n,&m,&w,&h);
/// w e pe ox , h e pe oy
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d%d%d",&c[i].x,&c[i].y,&c[i].r);
}
/// la ce raza incep sa fie conectate laturile intre ele??
for (i = 1 ; i < 4 ; i++){
for (j = i + 1 ; j <= 4 ; j++){
st = 0;
dr = 1000000000;
while (st <= dr){
mid = (st + dr)/2;
if (connect (i , j , mid))
dr = mid - 1;
else st = mid + 1;
}
val[i][j] = st; /// st e prima raza asa incat laturile i si j sunt conectate
}
}
for (i = 1 ; i <= m ; i++){
fscanf (fin,"%d%d",&r,&en);
if (en == 1){
fprintf (fout,"1");
if (val[1][4] <= r){
fprintf (fout,"\n");
continue;
}
if (min(val[1][2] , val[1][3]) > r)
fprintf (fout,"2");
if (min(val[2][4] , min(val[1][3] , val[2][3])) > r)
fprintf (fout,"3");
if (min(val[2][4] , val[3][4]) > r)
fprintf (fout,"4");
}
else if (en == 2){
if (val[1][2] <= r){
fprintf (fout,"2\n");
continue;
}
if (min(val[1][4] , val[1][3]) > r)
fprintf (fout,"1");
fprintf (fout,"2");
if (min(val[2][4] , val[2][3]) > r)
fprintf (fout,"3");
if (min(val[1][3] , min(val[2][4] , val[3][4])) > r)
fprintf (fout,"4");
}
else if (en == 3){
if (val[2][3] <= r){
fprintf (fout,"3\n");
continue;
}
if (min(val[2][4] , min(val[1][4] , val[1][3])) > r)
fprintf (fout,"1");
fprintf (fout,"3");
if (min(val[1][2] , val[2][4]) > r)
fprintf (fout,"2");
if (min(val[1][3] , val[3][4]) > r)
fprintf (fout,"4");
}
else if (en == 4){
if (val[3][4] <= r){
fprintf (fout,"4\n");
continue;
}
if (min(val[1][4] , val[2][4]) > r)
fprintf (fout,"1");
if (min(val[2][4] , min(val[1][2] , val[1][3])) > r)
fprintf (fout,"2");
if (min(val[1][3] , val[2][3]) > r)
fprintf (fout,"3");
fprintf (fout,"4");
}
fprintf (fout,"\n");
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:88:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d%d",&n,&m,&w,&h);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:91:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d%d",&c[i].x,&c[i].y,&c[i].r);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:113:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf (fin,"%d%d",&r,&en);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1977 ms |
892 KB |
Output is correct |
| 2 |
Incorrect |
1869 ms |
844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
2040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1977 ms |
892 KB |
Output is correct |
| 2 |
Incorrect |
1869 ms |
844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
