fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty