fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #define MAX_Y 10000;
  5. using namespace std;
  6. struct slide {
  7. 	double x1;
  8. 	double y1;
  9. 	double x2;
  10. 	double y2;
  11. };
  12. //высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
  13. double f (slide x, double x0) {
  14. 	double dx = x.x2 - x.x1;
  15. 	double dy = x.y2 - x.y1;
  16. 	return ((dy*(x0 - x.x1))/dx + x.y1);
  17. }
  18.  
  19. vector <slide> roof; //вектор всех крыш
  20.  
  21. //считывание и заполнение данных
  22. void read (int n) {
  23. 	while (n--) {
  24. 		double a, b, c, d;
  25. 		slide x;
  26. 		cin >> a >> b >> c >> d;
  27. 		if (a < c) {
  28. 			x.x1 = a;
  29. 			x.y1 = b;
  30. 			x.x2 = c;
  31. 			x.y2 = d;
  32. 		}
  33. 		else
  34. 		{
  35. 			x.x1 = c;
  36. 			x.y1 = d;
  37. 			x.x2 = a;
  38. 			x.y2 = b;
  39. 		}
  40. 		roof.push_back(x);
  41. 	}
  42. }
  43.  
  44. int main() {
  45. 	int n, x, y = MAX_Y + 1;
  46. 	slide a;
  47. 	cin >> x >> n;
  48. 	if (n == 0) {
  49. 		cout << x;
  50. 		return 0;
  51. 	}
  52. 	read (n);
  53. 	while (roof.size()) {
  54. 		int index = -1;
  55. 		int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
  56. 		bool no_projection = true;
  57. 		for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
  58. 			if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
  59. 				no_projection = false;
  60. 				if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
  61. 					value = f(roof[i], x);
  62. 					index = i;
  63. 				}
  64. 			}
  65. 			if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
  66. 				roof.erase(roof.begin() + i);
  67. 				i--;
  68. 			}
  69. 		}
  70. 		if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
  71. 			cout << x;
  72. 			return 0;
  73. 		}
  74. 		if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
  75. 			x = roof[index].x1;
  76. 		else
  77. 			x = roof[index].x2;
  78. 		y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
  79. 		roof.erase(roof.begin() + index);
  80. 	}
  81. 	cout << x;
  82. 	return 0;
  83. }
Runtime error #stdin #stdout 2.35s 2095880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MYup2d
rain
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!