fork download
  1. //#pragma optimization_level 3
  2. //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. //#pragma GCC target("avx,avx2,fma")
  5.  
  6.  
  7. #include <bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. typedef long long ll;
  13. typedef long double db;
  14. int inf = 1'000'000'007;
  15.  
  16. int vec_prod(int a, int b, int c, int d) {
  17. return a * d - b * c;
  18. }
  19.  
  20. int scal_prod(int a, int b, int c, int d) {
  21. return a * c + b * d;
  22. }
  23.  
  24. struct Point {
  25. int x, y;
  26. Point operator+(Point o) { return { x + o.x, y + o.y }; };
  27. Point operator-(Point o) { return { x - o.x, y - o.y }; };
  28. };
  29.  
  30. Point Get(Point a, Point b, Point c, int x, int y) { // Делим основание bc
  31. b = b - a; c = c - a;
  32. int dx = c.x - b.x, dy = c.y - b.y;
  33. // ans_x = b.x + dx * x / (x + y), ans_y = b.y + dy * x / (x + y)
  34. Point change = { b.x * (x + y) + dx * x, b.y * (x + y) + dy * x };
  35. return a + change;
  36. }
  37.  
  38. signed main()
  39. {
  40. ios_base::sync_with_stdio(false);
  41. cin.tie(0); cout.tie(0);
  42.  
  43. //srand(time(0));
  44. //srand(15);
  45. /*
  46. freopen("anniversary.in", "w", stdout);
  47. freopen("anniversary.out", "w", stdo);
  48. */
  49.  
  50. int n;
  51. cin >> n;
  52. vector<pair<int, int> > v(n);
  53. for(int c=0; c<n; c++)
  54. cin >> v[c].first >> v[c].second;
  55. //v.push_back(v[0]);
  56. for(int i=1; i<v.size(); i++){
  57. v[i].first -= v[0].first;
  58. v[i].second -= v[0].second;
  59. }
  60. pair<int, int> was = v[0];
  61. v[0].first = v[0].second = 0;
  62.  
  63. int Sall = 0;
  64. for(int c=1; c<n-1; c++) {
  65. Sall += vec_prod(v[c].first, v[c].second, v[c+1].first, v[c+1].second);
  66. }
  67. Sall = abs(Sall);
  68. int Snow = 0, pos = -1;
  69. for(int c=1; c<n-1; c++) {
  70. Snow += abs(vec_prod(v[c].first, v[c].second, v[c+1].first, v[c+1].second));
  71. //Snow = abs(Snow);
  72. if(Snow * 2 == Sall) {
  73. cout << was.first << " " << was.second << endl;
  74. cout << v[c+1].first + was.first << " " << v[c+1].second + was.second << endl;
  75. return 0;
  76. }
  77. if(Snow * 2 > Sall){
  78. pos = c+1;
  79. break;
  80. }
  81. }
  82. int under = Snow - abs(vec_prod(v[pos-1].first, v[pos-1].second, v[pos].first, v[pos].second));
  83. int over = Sall - under - abs(vec_prod(v[pos-1].first, v[pos-1].second, v[pos].first, v[pos].second));
  84. int triangle = abs(vec_prod(v[pos-1].first, v[pos-1].second, v[pos].first, v[pos].second));
  85. Point ans;
  86. if(under > over) {
  87. int give = under - over;
  88. int left = give*2 + triangle - give;
  89. int right = triangle - give;
  90. Point A = {0, 0};
  91. Point B = {v[pos].first, v[pos].second};
  92. Point C = {v[pos-1].first, v[pos-1].second};
  93. ans = Get(A, B, C, left, right);
  94. }
  95. else {
  96. int give = over - under;
  97. int left = triangle - give;
  98. int right = give*2 + triangle - give;
  99. Point A = {0, 0};
  100. Point B = {v[pos].first, v[pos].second};
  101. Point C = {v[pos-1].first, v[pos-1].second};
  102. ans = Get(A, B, C, left, right);
  103. }
  104. cout << was.first << " " << was.second << endl;
  105. cout << ans.x + was.first << " " << ans.y + was.second << endl;
  106. return 0;
  107. }
Runtime error #stdin #stdout #stderr 0s 4304KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc