#include <bits/stdc++.h>
#include <math.h>
using namespace std;
long long int n, m, w, h, r, e;
int pared_top, pared_right, pared_bottom, pared_left;
struct Tree {
long long int x, y, r;
};
struct Arista {
int nodo, lenght;
};
Tree trees[2002];
vector <Arista> grafo[2008];
int output[100002];
bool visited[2008];
/**
struct Question {
int corner, order;
long long int r;
};
Question questions[100002];
*/
queue<long long int> queue_points;
void findpaths(int start, long long int maxsize)
{
memset(visited, 0, sizeof visited);
queue_points.push(start);
visited[start] = true;
while (!queue_points.empty()) // y marco elementos hasta que la cola este vacia
{
int x = queue_points.front(); // saco el proximo de la cola
queue_points.pop();
for (int i = 0; i<grafo[x].size(); i++)
if (!visited[ grafo[x][i].nodo ])
{
if (grafo[x][i].lenght <= maxsize)
{
queue_points.push(grafo[x][i].nodo);
visited[grafo[x][i].nodo] = true;
}
else
break;
}
}
}
bool compareInterval(Arista i1, Arista i2)
{
return (i1.lenght < i2.lenght);
}
void create_graph()
{
Arista a;
for (int i = 1; i <= n; i++)
{
for (int j = i+1; j <= n; j++)
{
a.nodo = i;
a.lenght = sqrt( pow(trees[i].x-trees[j].x,2.0) + pow(trees[i].y-trees[j].y,2.0) ); // - trees[i].r - trees[j].r;
grafo[j].push_back(a);
a.nodo = j;
grafo[i].push_back(a);
}
// 0,0 es abajo-izquierda
a.nodo = i;
a.lenght = trees[i].y - trees[i].r;
grafo[pared_bottom].push_back(a);
a.nodo = pared_bottom;
grafo[i].push_back(a);
a.nodo = i;
a.lenght = h - trees[i].y - trees[i].r;
grafo[pared_top].push_back(a);
a.nodo = pared_top;
grafo[i].push_back(a);
a.nodo = i;
a.lenght = trees[i].x - trees[i].r;
grafo[pared_left].push_back(a);
a.nodo = pared_left;
grafo[i].push_back(a);
a.nodo = i;
a.lenght = w - trees[i].x - trees[i].r;
grafo[pared_right].push_back(a);
a.nodo = pared_right;
grafo[i].push_back(a);
}
for (int i = 1; i <= n+4; i++)
sort(grafo[i].begin(),grafo[i].end(),compareInterval);
}
int main()
{
cin >> n >> m >> w >> h;
pared_top = n+1;
pared_right = n+2;
pared_bottom = n+3;
pared_left= n+4;
for (int i = 1; i <= n; i++)
cin >> trees[i].x >> trees[i].y >> trees[i].r;
create_graph();
/**
for (int i = 1; i <= n+4; i++)
{
int kk = grafo[i].size();
for (int j = 0; j < grafo[i].size(); j++)
cout << "(" << grafo[i][j].nodo << "," << grafo[i][j].lenght << ") ";
cout << "\n";
}
*/
for (int i = 1; i <= m; i++)
{
cin >> r >> e;
r = r * 2;
int p1 = 1;
int p2 = 2;
int p3 = 3;
int p4 = 4;
findpaths(pared_top,r);
if (e==1)
{
if (visited[pared_bottom]) { p3 = 0; p2 = 0; }
if (visited[pared_right]) p3 = 0;
if (visited[pared_left]) p4 = 0;
}
else if (e==2)
{
if (visited[pared_bottom]) { p4 = 0; p1 = 0; }
if (visited[pared_right]) p3 = 0;
if (visited[pared_left]) p4 = 0;
}
else if (e==3)
{
if (visited[pared_bottom]) { p4 = 0; p1 = 0; }
if (visited[pared_right]) { p1 = 0; p2 = 0; p4 = 0;}
if (visited[pared_left]) p4 = 0;
}
else if (e==4)
{
if (visited[pared_bottom]) { p2 = 0; p3 = 0; }
if (visited[pared_right]) p3 = 0;
if (visited[pared_left]) { p1 = 0; p2 = 0; p3 = 0; }
}
if (p1+p2+p3+p4 > 1)
{
findpaths(pared_right,r);
if (e==1)
{
if (visited[pared_bottom]) p2 = 0;
if (visited[pared_left]) { p3 = 0; p4 = 0; }
}
else if (e==2)
{
if (visited[pared_bottom]) {p1 = 0; p3 = 0; p4 = 0;}
if (visited[pared_left]) { p3 = 0; p4 = 0; }
}
else if (e==3)
{
if (visited[pared_bottom]) p2 = 0;
if (visited[pared_left]) { p1 = 0; p2 = 0; }
}
else if (e==4)
{
if (visited[pared_bottom]) p2 = 0;
if (visited[pared_left]) { p1 = 0; p2 = 0; }
}
}
if (p1+p2+p3+p4 > 1)
{
findpaths(pared_bottom,r);
if (e==1)
{
if (visited[pared_left]) { p2 = 0; p3 = 0; p4 = 0; }
}
else if (e==2)
{
if (visited[pared_left]) { p1 = 0; }
}
else if (e==3)
{
if (visited[pared_left]) { p1 = 0; }
}
else if (e==4)
{
if (visited[pared_left]) { p1 = 0; }
}
}
if (p1 != 0) output[i] = output[i] * 10 + p1;
if (p2 != 0) output[i] = output[i] * 10 + p2;
if (p3 != 0) output[i] = output[i] * 10 + p3;
if (p4 != 0) output[i] = output[i] * 10 + p4;
}
for (int i = 1; i <= m; i++)
cout << output[i] << "\n";
return 0;
}
Compilation message
park.cpp: In function 'void findpaths(int, long long int)':
park.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Arista>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i<grafo[x].size(); i++)
| ~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
307 ms |
32884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
123 ms |
2640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
307 ms |
32884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
