fork download
copy 
  1. #include<stdio.h>
  2. #include<set>
  3. #include<vector>
  4. #include<deque>
  5. using namespace std;
  6. struct xy {
  7. 	int x[2], w;
  8. 	bool operator<(const xy p)const {
  9. 		if (x[0] != p.x[0])return x[0] < p.x[0];
  10. 		if (x[1] != p.x[1])return x[1] < p.x[1];
  11. 		return w < p.w;
  12. 	}
  13. }a[121212];
  14. set<xy>S[4];
  15. int NT[121212][4], dist[121212][4];
  16. int min(int a, int b) { if (a == -1)return b; if (a < b)return a; return b; }
  17. int main() {
  18. 	int n, i, j;
  19. 	scanf("%d", &n);
  20. 	n += 2;
  21. 	for (i = 0; i < n; i++) scanf("%d%d", &a[i].x[0], &a[i].x[1]);
  22. 	for (i = 0; i < n; i++) for (j = 0; j < 4; j++)NT[i][j] = dist[i][j] = -1;
  23. 	for (i = 0; i < 4; i++) for (j = 0; j < n; j++) S[i].insert({ { a[j].x[i % 2],((i / 2) * 2 - 1) * a[j].x[!(i % 2)] },j });
  24. 	for (i = 0; i < 4; i++) {
  25. 		set<xy>::iterator it, next;
  26. 		for (it = S[i].begin();;) {
  27. 			next = it;next++;
  28. 			if (next == S[i].end())break;
  29. 			if (it->x[0] == next->x[0]) NT[it->w][i] = next->w;
  30. 			it = next;
  31. 		}
  32. 	}
  33. 	deque<int>Qx[2], Qy[2];
  34. 	for (i = 0; i < 4; i++)if(NT[0][i]!=-1)Qx[0].push_back(0), Qy[0].push_back(i),dist[0][i]=0;
  35. 	int now = 0;
  36. 	while (!Qx[0].empty()||!Qx[1].empty()) {
  37. 		if (Qx[now].empty())now=!now;
  38. 		int nowx = Qx[now].front(); Qx[now].pop_front();
  39. 		int nowy = Qy[now].front(); Qy[now].pop_front();
  40. 		for (i = -1; i <= 1; i++) {
  41. 			int ny = (nowy + i + 4) % 4;
  42. 			int nx = NT[nowx][nowy];
  43. 			if (nx == 1)
  44. 				int sp = 1;
  45. 			if (nx == -1 || dist[nx][ny] != -1)continue;
  46. 			Qx[now^(!!i)].push_back(nx), Qy[now^(!!i)].push_back(ny);
  47. 			dist[nx][ny] = dist[nowx][nowy] + !!i;
  48. 		}
  49. 	}
  50. 	int ans = -1;
  51. 	for (i = 0; i < 4; i++) {
  52. 		if (dist[1][i] == -1)continue;
  53. 		ans = min(ans, dist[1][i]);
  54. 	}
  55. 	printf("%d", ans);
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 4240KB
comments (?)
stdin
copy 
4 0 0 7 2
3 2
0 2
1 6
3 0
stdout
copy 
1
https://ideone.com/8ZsEsG
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!