Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef pair<int, int> pii;
- #define X first
- #define Y second
- #define mk make_pair
- #define inb push_back
- #define all(v) v.begin(), v.end()
- const double eps = 1e-6;
- const int BP = 100;
- bool eq(double a, double b)
- {
- return abs(a - b) <= eps;
- }
- double dist(pair<double, double> a, pair<double, double> b)
- {
- return (a.X - b.X) * (a.X - b.X) + (a.Y - b.Y) * (a.Y - b.Y);
- }
- int main()
- {
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n;
- double w;
- cin >> w >> n;
- if (n == 0) cout << w / 2 << ' ' << 0, exit(0);
- vector<pair<double, double> > a(n);
- for(int i = 0; i < n; ++i)
- cin >> a[i].X >> a[i].Y;
- vector<vector<double> > dp(n, vector<double>(2));
- for(int i = 0; i < n; ++i)
- {
- dp[i][0] = a[i].X * a[i].X;
- dp[i][1] = a[i].X * a[i].X / 4;
- }
- vector<vector<bool> > us(n, vector<bool>(2));
- vector<vector<pii> > p(n, vector<pii>(2));
- for(int i = 0; i < n; ++i) p[i][0].X = p[i][1].X = -1;
- double ans = w * w / 4;
- int g, h;
- double c = w / 2, d = 0;
- for(int q = 0; q < n * 2; ++q)
- {
- double mn = 2e9;
- int i, l;
- for(int j = 0; j < n; ++j)
- for(int k = 0; k < 2; ++k)
- if (!us[j][k] && dp[j][k] < mn)
- mn = dp[j][k], i = j, l = k;
- us[i][l] = 1;
- if (!l && max(dp[i][l], (w - a[i].X) * (w - a[i].X) / 4) < ans)
- ans = max(dp[i][l], (w - a[i].X) * (w - a[i].X) / 4), g = i, h = l;
- else if (max(dp[i][l], (w - a[i].X) * (w - a[i].X)) < ans)
- ans = max(dp[i][l], (w - a[i].X) * (w - a[i].X)), g = i, h = l;
- for(int j = 0; j < n; ++j)
- {
- if (!l)
- {
- if (max(dp[i][l], dist(a[i], a[j])) < dp[j][0])
- dp[j][0] = max(dp[i][l], dist(a[i], a[j])), p[j][0] = { i, 0 };
- if (max(dp[i][l], dist(a[i], a[j]) / 4) < dp[j][1])
- dp[j][1] = max(dp[i][l], dist(a[i], a[j]) / 4), p[j][1] = { i, 0 };
- }
- else
- {
- if (max(dp[i][l], dist(a[i], a[j])) < dp[j][1])
- dp[j][1] = max(dp[i][l], dist(a[i], a[j])), p[j][1] = { i, 1 };
- }
- }
- }
- int l = g, r = h;
- while(p[l][r].X != -1)
- {
- g = p[l][r].X, h = p[l][r].Y;
- if (h != r) c = (a[l].X + a[g].X) / 2, d = (a[l].Y + a[g].Y) / 2;
- l = g, r = h;
- }
- cout << c << ' ' << d;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement