Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <cmath>
- #include <string>
- #include <algorithm>
- #include <string>
- #include <deque>
- #include <iomanip>
- #define F first
- #define S second
- using namespace std;
- const long double eps2 = 0.0000005;
- const long double eps1 = 1e-5;
- const long double pi = 3.1415926535897932;
- struct point
- {
- long double x;
- long double y;
- long double v;
- point()
- {
- x = 0.0;
- y = 0.0;
- v = 0.0;
- }
- point(long double _x, long double _y)
- {
- x = _x;
- y = _y;
- v = -1.0;
- }
- point(long double _x, long double _y, long double _v)
- {
- x = _x;
- y = _y;
- v = _v;
- }
- };
- struct line
- {
- long double a;
- long double b;
- long double c;
- line()
- {
- a = 0.0;
- b = 0.0;
- c = 0.0;
- }
- line(point _a, point _b)
- {
- a = _b.y - _a.y;
- b = _a.x - _b.x;
- c = b * _a.y - a * _a.x;
- }
- };
- vector<point> a;
- int n;
- long double t, d;
- point ans;
- point operator+(point a, point b)
- {
- return point(a.x + b.x, a.y + b.y, a.v + b.v);
- }
- point operator-(point a, point b)
- {
- return point(a.x - b.x, a.y - b.y, a.v - b.v);
- }
- point operator*(point a, long double k)
- {
- return point(a.x * k, a.y * k, a.v * k);
- }
- point operator/(point a, long double k)
- {
- return point(a.x / k, a.y / k, a.v / k);
- }
- long double scal(point a, point b)
- {
- return a.x * b.x + a.y * b.y;
- }
- long double vect(point a, point b)
- {
- return a.x * b.y - a.y * b.x;
- }
- long double dist(point a, point b)
- {
- return sqrt(scal(a - b, a - b));
- }
- //bool out(point b, point e)
- //{
- // if (dist(b, point()) > d && dist(e, point()) > d && dist(point(b.x, e.y), point()) > d && dist(point(e.x, b.y), point()) > d)
- // return false;
- // return true;
- //}
- bool in(point g, point c)
- {
- double r = c.v * t;
- if (c.v == -1.0)
- r = d;
- if (r - dist(g, c) > -eps1)
- return true;
- return false;
- }
- void find(point b, point e, point &ans)
- {
- /*if (out(point b, point e))
- return;*/
- if (ans.v == 1)
- return;
- if (!in(b, point(0, 0)) && !in(e, point(0, 0)) && !in(point(b.x, e.y), point(0, 0)) && !in(point(e.x, b.y), point(0, 0)))
- return;
- for (int i = 0; i < n; i++)
- {
- if (in(b, a[i]) && in(e, a[i]) && in(point(b.x, e.y), a[i]) && in(point(e.x, b.y), a[i]))
- return;
- }
- if (dist(e, b) < eps1)
- {
- ans = e;
- ans.v = 1;
- return;
- }
- find(b, point((e.x + b.x) / 2, (e.y + b.y) / 2), ans);
- find(point((e.x + b.x) / 2, (e.y + b.y) / 2), e, ans);
- find(point((e.x + b.x) / 2, b.y), point(e.x, (e.y + b.y) / 2), ans);
- find(point(b.x, (e.y + b.y) / 2), point((e.x + b.x) / 2, e.y), ans);
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- int n;
- long double x, y, v;
- cin >> d >> n;
- d /= 2;
- for (int i = 0; i < n; i++)
- {
- cin >> x >> y >> v;
- a.push_back(point(x, y, v));
- }
- long double l = 0.0, r = 2000001.0;
- while (r - l > eps2)
- {
- t = (l + r) / 2;
- find(point(-d, 0.0), point(d, d), ans);
- if (ans.v == 1)
- l = t;
- else
- r = t;
- }
- cout << fixed;
- cout << setprecision(5) << l << endl;
- cout << setprecision(5) << ans.x << " " << ans.y << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement