fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/0CWKP6
language:
C++14 (gcc 8.3)
created:
3 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!